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