POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC

DOI10.1142/S0219061309000847zbMath1204.03056MaRDI QIDQ3583040

Arnold Beckmann, Samuel R. Buss

Publication date: 26 August 2010

Published in: Journal of Mathematical Logic (Search for Journal in Brave)

zbMATH Keywords

bounded arithmeticproof complexitySkolem functionprovably totalpolynomial local searchwitnessing

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Related Items (12)

Approximate counting and NP search problems ⋮ FRAGMENTS OF APPROXIMATE COUNTING ⋮ Mining the surface: witnessing the low complexity theorems of arithmetic ⋮ The provably total NP search problems of weak second order bounded arithmetic ⋮ Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem ⋮ INCOMPLETENESS IN THE FINITE DOMAIN ⋮ Improved witnessing and local improvement principles for second-order bounded arithmetic ⋮ Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\) ⋮ Nested PLS ⋮ A Characterisation of Definable NP Search Problems in Peano Arithmetic ⋮ Alternating minima and maxima, Nash equilibria and bounded arithmetic ⋮ Feasible functionals and intersection of ramified types

Cites Work

• On the computational complexity of cut-reduction
• How easy is local search?
• Structure and definability in general bounded arithmetic theories
• Bounded arithmetic and the polynomial hierarchy
• Relating the bounded arithmetic and polynomial time hierarchies
• Separation results for the size of constant-depth propositional proofs
• Quantified propositional calculi and fragments of bounded arithmetic
• NP search problems in low fragments of bounded arithmetic
• Fragments of bounded arithmetic and the lengths of proofs
• Existence and feasibility in arithmetic
• Notes on polynomially bounded arithmetic

This page was built for publication: POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC