Quantified propositional calculi and fragments of bounded arithmetic
From MaRDI portal
Publication:3472099
DOI10.1002/MALQ.19900360106zbMATH Open0696.03031OpenAlexW2161149481WikidataQ106785088 ScholiaQ106785088MaRDI QIDQ3472099FDOQ3472099
Authors: Jan Krajíček, Pavel Pudlák 
Publication date: 1990
Published in: Zeitschrift für Mathematische Logik und Grundlagen der Mathematik (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/malq.19900360106
Recommendations
- Examining Fragments of the Quantified Propositional Calculus
- On the provability logic of bounded arithmetic
- scientific article; zbMATH DE number 819737
- scientific article; zbMATH DE number 4010488
- Propositional quantification in the monadic fragment of intuitionistic logic
- Fragments of bounded arithmetic and the lengths of proofs
- scientific article; zbMATH DE number 4099258
- Computations in fragments of intuitionistic propositional logic
- scientific article; zbMATH DE number 2015268
- Predicate logics of decidable fragments of arithmetic
Cited In (36)
- Towards a unified complexity theory of total functions
- Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\)
- Fragments of bounded arithmetic and the lengths of proofs
- Computations in fragments of intuitionistic propositional logic
- Simulating non-prenex cuts in quantified propositional calculus
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- Classes of representable disjoint \textsf{NP}-pairs
- Tuples of disjoint \(\mathsf{NP}\)-sets
- Towards Uniform Certification in QBF
- Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic
- Examining Fragments of the Quantified Propositional Calculus
- Preservation theorems and restricted consistency statements in bounded arithmetic
- Mathematical logic: proof theory, constructive mathematics. Abstracts from the workshop held November 12--17, 2023
- Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
- Witnessing functions in bounded arithmetic and search problems
- Expansion-based QBF solving versus Q-resolution
- On the finite axiomatizability of \(\forall\hat{\Sigma}^{\mathrm{b}}_1 (\hat{\mathsf{R}}^1_2)\)
- Some consequences of cryptographical conjectures for \(S_2^1\) and EF
- Circuit principles and weak pigeonhole variants
- On induction-free provability
- Tautologies from pseudo-random generators
- Title not available (Why is that?)
- Separation results for the size of constant-depth propositional proofs
- Lifting lower bounds for tree-like proofs
- Slicewise Definability in First-Order Logic with Bounded Quantifier Rank.
- On the correspondence between arithmetic theories and propositional proof systems – a survey
- Witnessing flows in arithmetic
- Bounded arithmetic and the polynomial hierarchy
- Implicit proofs
- Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem
- Tractable fragments of Presburger arithmetic
- Logical Closure Properties of Propositional Proof Systems
- Dual weak pigeonhole principle, Boolean complexity, and derandomization
- On transformations of constant depth propositional proofs
- Induction rules in bounded arithmetic
- On an optimal quantified propositional proof system nal proof system and a complete language for NP ∩ co-NP for NP ∩ co-NP
This page was built for publication: Quantified propositional calculi and fragments of bounded arithmetic
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3472099)
