The complexity of the disjunction and existential properties in intuitionistic logic

DOI10.1016/S0168-0072(99)00002-0zbMath0939.03064OpenAlexW1972606747MaRDI QIDQ1304542

Samuel R. Buss, Grigori Mints

Publication date: 15 February 2000

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

Full work available at URL: https://doi.org/10.1016/s0168-0072(99)00002-0

zbMATH Keywords

complexityintuitionistic logicdisjunction propertyexistential propertyfragment of arithmetic

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Intuitionistic mathematics (03F55) Complexity of proofs (03F20)

Related Items

Proof complexity of intuitionistic implicational formulas ⋮ A lower bound for intuitionistic logic ⋮ INCOMPLETENESS IN THE FINITE DOMAIN ⋮ On the computational content of intuitionistic propositional proofs ⋮ Frege systems for extensible modal 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
• Lower bounds for increasing complexity of derivations after cut elimination
• Intuitionistic propositional logic is polynomial-space complete
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• Lower Bounds on Herbrand's Theorem