POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC
From MaRDI portal
Publication:3583040
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)
bounded arithmetic; proof complexity; Skolem function; provably total; polynomial local search; witnessing
03D15: Complexity of computation (including implicit computational complexity)
03F30: First-order arithmetic and fragments
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
03F20: Complexity of proofs
Related Items
INCOMPLETENESS IN THE FINITE DOMAIN, Approximate counting and NP search problems, Improved witnessing and local improvement principles for second-order bounded arithmetic, Mining the surface: witnessing the low complexity theorems of arithmetic, Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\), Nested PLS, 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, Alternating minima and maxima, Nash equilibria and bounded arithmetic, Feasible functionals and intersection of ramified types, FRAGMENTS OF APPROXIMATE COUNTING, A Characterisation of Definable NP Search Problems in Peano Arithmetic
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
