A lower bound for intuitionistic logic

DOI10.1016/j.apal.2007.01.001zbMath1115.03081OpenAlexW2017209655MaRDI QIDQ876385

Pavel Hrubeš

Publication date: 18 April 2007

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2007.01.001

zbMATH Keywords

modal logicintuitionistic logicproof complexityFrege system

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Complexity of computation (including implicit computational complexity) (03D15) Complexity of proofs (03F20) Intermediate logics (03B55)

Related Items (9)

Logic of Intuitionistic Interactive Proofs (Formal Theory of Perfect Knowledge Transfer) ⋮ Proof complexity of intuitionistic implicational formulas ⋮ Towards NP-P via proof complexity and search ⋮ Generalisation of proof simulation procedures for Frege systems by M.L. Bonet and S.R. Buss ⋮ Proof complexity of substructural logics ⋮ On lengths of proofs in non-classical logics ⋮ Proof Complexity of Non-classical Logics ⋮ Substitution Frege and extended Frege proof systems in non-classical logics ⋮ On the proof complexity of logics of bounded branching

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The monotone circuit complexity of Boolean functions
• The ellipsoid method and its consequences in combinatorial optimization
• Intuitionistic propositional logic is polynomial-space complete
• The complexity of the disjunction and existential properties in intuitionistic logic
• The gap between monotone and non-monotone circuit complexity is exponential
• Polynomial size proofs of the propositional pigeonhole principle
• Speed-Up by Theories with Infinite Models
• Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
• Lower bounds for modal logics

This page was built for publication: A lower bound for intuitionistic logic