Complexity of intuitionistic propositional logic and its fragments
DOI10.3166/jancl.18.267-292zbMath1181.03006OpenAlexW2008892119MaRDI QIDQ3643316
Publication date: 11 November 2009
Published in: Journal of Applied Non-Classical Logics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.3166/jancl.18.267-292
complexitypropositional logicintuitionistic logicdecision problemPSPACE-completenesscomplexity function
Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) History of mathematical logic and foundations (03-03) Subsystems of classical logic (including intuitionistic logic) (03B20)
Related Items (6)
Cites Work
- A propositional logic with explicit fixed points
- On fragments of Medvedev's logic
- A guide to completeness and complexity for modal logics of knowledge and belief
- Propositional dynamic logic of regular programs
- Intuitionistic propositional logic is polynomial-space complete
- The price of universality
- The effect of bounding the number of primitive propositions and the depth of nesting on the complexity of modal logic
- Relationships between nondeterministic and deterministic tape complexities
- Classifying the computational complexity of problems
- On formulas of one variable in intuitionistic propositional calculus
- The Computational Complexity of Provability in Systems of Modal Propositional Logic
- THE CALCULUS OF THE WEAK "LAW OF EXCLUDED MIDDLE"
- The decidability of the Kreisel-Putnam system
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Complexity of intuitionistic propositional logic and its fragments