Complexity of intuitionistic propositional logic and its fragments

DOI10.3166/jancl.18.267-292zbMath1181.03006OpenAlexW2008892119MaRDI QIDQ3643316

Mikhail Rybakov

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

zbMATH Keywords

complexitypropositional logicintuitionistic logicdecision problemPSPACE-completenesscomplexity function

Mathematics Subject Classification ID

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)

Undecidability of QLTL and QCTL with two variables and one monadic predicate letter ⋮ Complexity of finite-variable fragments of propositional temporal and modal logics of computation ⋮ Computational complexity of the word problem in modal and Heyting algebras with a small number of generators ⋮ Бинарный предикат, транзитивное замыкание, две-три переменные: сыграем в домино? ⋮ Proof theory for positive logic with weak negation ⋮ Undecidability of first-order modal and intuitionistic logics with two variables and one monadic predicate letter

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