Relating the bounded arithmetic and polynomial time hierarchies

DOI10.1016/0168-0072(94)00057-AzbMath0829.03035WikidataQ126372038 ScholiaQ126372038MaRDI QIDQ1899144

Samuel R. Buss

Publication date: 4 October 1995

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

zbMATH Keywords

bounded arithmeticfinite axiomatizabilitypolynomial time hierarchy

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30)

Related Items

Truth definitions without exponentiation and the Σ₁ collection scheme ⋮ Separations of first and second order theories in bounded arithmetic ⋮ Preservation theorems and restricted consistency statements in bounded arithmetic ⋮ End extensions of models of linearly bounded arithmetic ⋮ On parallel hierarchies and R ki ⋮ A second-order system for polytime reasoning based on Grädel's theorem. ⋮ Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem ⋮ A note on the Σ₁collection scheme and fragments of bounded arithmetic ⋮ 2000 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium 2000 ⋮ Approximate counting in bounded arithmetic ⋮ POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC ⋮ A model of \(\widehat{R}^2_3\) inside a subexponential time resource ⋮ Consequences of the provability of NP ⊆ P/poly ⋮ On the correspondence between arithmetic theories and propositional proof systems – a survey ⋮ On Herbrand's theorem ⋮ Induction rules in bounded arithmetic ⋮ Approximate counting by hashing in bounded arithmetic ⋮ A model-theoretic characterization of the weak pigeonhole principle

Cites Work

• Turing machines that take advice
• On the scheme of induction for bounded arithmetic formulas
• On truth-table reducibility to SAT
• Bounded arithmetic and the polynomial hierarchy
• Fragments of Bounded Arithmetic and Bounded Query Classes
• An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
• Existence and feasibility in arithmetic
• Notes on polynomially bounded arithmetic
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item