Bounded arithmetic and the polynomial hierarchy
From MaRDI portal
Publication:1177041
DOI10.1016/0168-0072(91)90043-LzbMath0736.03022OpenAlexW2071204190WikidataQ106785050 ScholiaQ106785050MaRDI QIDQ1177041
Gaisi Takeuti, Pavel Pudlák, Jan Krajíček
Publication date: 25 June 1992
Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0168-0072(91)90043-l
Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30)
Related Items
Binary models generated by their tally part ⋮ Separations of theories in weak bounded arithmetic ⋮ On induction-free provability ⋮ Circuit principles and weak pigeonhole variants ⋮ Relating the bounded arithmetic and polynomial time hierarchies ⋮ What are the \(\forall \Sigma_ 1^ b\)-consequences of \(T_ 2^ 1\) and \(T_ 2^ 2\)? ⋮ Separations of first and second order theories in bounded arithmetic ⋮ FRAGMENTS OF APPROXIMATE COUNTING ⋮ Preservation theorems for bounded formulas ⋮ Typical forcings, NP search problems and an extension of a theorem of Riis ⋮ On parallel hierarchies and \(R_k^i\) ⋮ Some consequences of cryptographical conjectures for \(S_2^1\) and EF ⋮ On parallel hierarchies and R ki ⋮ Some consequences of cryptographical conjectures for S 2 1 and EF ⋮ Provably total functions of intuitionistic bounded arithmetic ⋮ On the finite axiomatizability of ⋮ Mining the surface: witnessing the low complexity theorems of arithmetic ⋮ ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS ⋮ A second-order system for polytime reasoning based on Grädel's theorem. ⋮ END-EXTENSIONS OF MODELS OF WEAK ARITHMETIC FROM COMPLEXITY-THEORETIC CONTAINMENTS ⋮ Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem ⋮ Notes on polynomially bounded arithmetic ⋮ Circuit lower bounds in bounded arithmetics ⋮ A Tight Karp-Lipton Collapse Result in Bounded Arithmetic ⋮ Bounded theories for polyspace computability ⋮ Lifting lower bounds for tree-like proofs ⋮ INCOMPLETENESS IN THE FINITE DOMAIN ⋮ Tautologies from Pseudo-Random Generators ⋮ Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\) ⋮ Approximate counting in bounded arithmetic ⋮ POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC ⋮ Feasibly constructive proofs of succinct weak circuit lower bounds ⋮ A model of \(\widehat{R}^2_3\) inside a subexponential time resource ⋮ A simple proof of Parsons' theorem ⋮ 1998–99 Annual Meeting of the Association for Symbolic Logic ⋮ A generalization of the second incompleteness theorem and some exceptions to it ⋮ Consequences of the provability of NP ⊆ P/poly ⋮ Polynomial time ultrapowers and the consistency of circuit lower bounds ⋮ Examining Fragments of the Quantified Propositional Calculus ⋮ On the correspondence between arithmetic theories and propositional proof systems – a survey ⋮ On Herbrand's theorem ⋮ Unnamed Item ⋮ Induction rules in bounded arithmetic ⋮ ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION ⋮ Approximate counting by hashing in bounded arithmetic ⋮ Fragments of bounded arithmetic and the lengths of proofs ⋮ Models of replacement schemes ⋮ Witnessing functions in bounded arithmetic and search problems ⋮ Unprovability of circuit upper bounds in Cook's theory PV
Cites Work
- Unnamed Item
- Unnamed Item
- On the scheme of induction for bounded arithmetic formulas
- Quantified propositional calculi and fragments of bounded arithmetic
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Provability of the pigeonhole principle and the existence of infinitely many primes
- Proof theory
