Intuitionistic propositional logic is polynomial-space complete
From MaRDI portal
Cites work
- scientific article; zbMATH DE number 3485758 (Why is no real title available?)
- scientific article; zbMATH DE number 3557241 (Why is no real title available?)
- scientific article; zbMATH DE number 3222098 (Why is no real title available?)
- scientific article; zbMATH DE number 3248792 (Why is no real title available?)
- scientific article; zbMATH DE number 3275554 (Why is no real title available?)
- scientific article; zbMATH DE number 3280068 (Why is no real title available?)
- scientific article; zbMATH DE number 3300581 (Why is no real title available?)
- scientific article; zbMATH DE number 3073037 (Why is no real title available?)
- The polynomial-time hierarchy
- The typed lambda-calculus is not elementary recursive
Cited in
(67)- From QBFs to \textsf{MALL} and back via focussing
- Some pitfalls of \textsf{LK}-to-\textsf{LJ} translations and how to avoid them
- A unifying framework for type inhabitation
- Optimization techniques for propositional intuitionistic logic and their implementation
- The emptiness problem for intersection types
- DECIDABILITY OF ADMISSIBILITY: ON A PROBLEM BY FRIEDMAN AND ITS SOLUTION BY RYBAKOV
- Complexity of some problems in positive and related calculi
- A tableau calculus for Propositional Intuitionistic Logic with a refined treatment of nested implications
- A selected bibliography on constructive mathematics, intuitionistic type theory and higher order deduction
- Pre-grammars and inhabitation for a subset of rank 2 intersection types
- Implicational relevance logic is 2-\textsc{ExpTime}-complete
- Admissible rules in the implication-negation fragment of intuitionistic logic
- Rules with parameters in modal logic. II.
- Synthesis of modality definitions and a theorem prover for epistemic intuitionistic logic
- Linearizing intuitionistic implication
- Disjunction property and complexity of substructural logics
- Complexity of admissible rules
- Studying provability in implicational intuitionistic logic: the formula tree approach
- Substitutions of \(\Sigma_1^0\)-sentences: Explorations between intuitionistic propositional logic and intuitionistic arithmetic
- Partial algebras and complexity of satisfiability and universal theory for distributive lattices, Boolean algebras and Heyting algebras
- Graph decompositions and tree automata in reasoning with uncertainty
- The complexity of Horn fragments of linear logic
- Plug and Play Negations
- The typed lambda-calculus is not elementary recursive
- \(\lambda\)-definability of free algebras
- Partial up an down logic
- Proof theory for positive logic with weak negation
- Satisfiability in many-valued sentential logic is NP-complete
- scientific article; zbMATH DE number 7204434 (Why is no real title available?)
- Computational complexity for bounded distributive lattices with negation
- Intuitionistic Decision Procedures Since Gentzen
- The consequence relation in the logic of commutative GBL-algebras is PSPACE-complete
- Undecidability of propositional separation logic and its neighbours
- Sequent Calculus for Intuitionistic Epistemic Logic IEL
- Typing in reflective combinatory logic
- Infiniteness of \(\text{proof}(\alpha)\) is polynomial-space complete
- Logic of intuitionistic interactive proofs (formal theory of perfect knowledge transfer)
- Propositional logics complexity and the sub-formula property
- scientific article; zbMATH DE number 7455712 (Why is no real title available?)
- Deriving efficient sequential and parallel generators for closed simply-typed lambda terms and normal forms
- An informational view of classical logic
- Proof finding algorithms for implicational logics
- An \(\mathsf{AC}^{1}\)-complete model checking problem for intuitionistic logic
- On the existence of closed terms in the typed lambda calculus II: Transformations of unification problems
- Lower end of the linial-post spectrum
- Complexity of intuitionistic propositional logic and its fragments
- A lower bound for intuitionistic logic
- How many times do we need an assumption to prove a tautology in minimal logic? Examples on the compression power of classical reasoning
- Contraction-free linear depth sequent calculi for intuitionistic propositional logic with the subformula property and minimal depth counter-models
- On Church's formal theory of functions and functionals. The - calculus: Connections to higher type recursion theory, proof theory, category theory
- Hypothetical datalog: Complexity and expressibility
- Complexity of interpolation and related problems in positive calculi
- Proof compression and NP versus PSPACE. II
- Unification under a mixed prefix
- Sufficient conditions for cut elimination with complexity analysis
- The complexity of the disjunction and existential properties in intuitionistic logic
- Computational complexity of the word problem in modal and Heyting algebras with a small number of generators
- On the polynomial-space completeness of intuitionistic propositional logic
- Complexity of some language fragments of fuzzy logics
- Tarski's theorem on intuitionistic logic, for polyhedra
- Proof compression and NP versus PSPACE
- Stable philosophical systems and radical anti-realism
- Mereotopology in 2nd-order and modal extensions of intuitionistic propositional logic
- Proof-search in intuitionistic logic based on constraint satisfaction
- Proof Compression and NP Versus PSPACE II: Addendum
- Exploring the relation between Intuitionistic BI and Boolean BI: an unexpected embedding
- A Survey of the Proof-Theoretic Foundations of Logic Programming
This page was built for publication: Intuitionistic propositional logic is polynomial-space complete
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1259589)
