Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic
DOI10.1142/S0219061309000847zbMATH Open1204.03056MaRDI QIDQ3583040FDOQ3583040
Authors: Arnold Beckmann, Samuel R. Buss 
Publication date: 26 August 2010
Published in: Journal of Mathematical Logic (Search for Journal in Brave)
Recommendations
- Characterising definable search problems in bounded arithmetic via proof notations
- NP search problems in low fragments of bounded arithmetic
- Witnessing functions in bounded arithmetic and search problems
- Bounded arithmetic and the polynomial hierarchy
- On Search Problems in Complexity Theory and in Logic (Abstract)
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20) First-order arithmetic and fragments (03F30) Complexity of computation (including implicit computational complexity) (03D15)
Cites Work
- Notes on polynomially bounded arithmetic
- Existence and feasibility in arithmetic
- How easy is local search?
- Separation results for the size of constant-depth propositional proofs
- Bounded arithmetic and the polynomial hierarchy
- Quantified propositional calculi and fragments of bounded arithmetic
- Structure and definability in general bounded arithmetic theories
- NP search problems in low fragments of bounded arithmetic
- Fragments of bounded arithmetic and the lengths of proofs
- Relating the bounded arithmetic and polynomial time hierarchies
- On the computational complexity of cut-reduction
Cited In (21)
- NP search problems in low fragments of bounded arithmetic
- Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\)
- Nested PLS
- An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
- Fragments of approximate counting
- Improved witnessing and local improvement principles for second-order bounded arithmetic
- A Characterisation of Definable NP Search Problems in Peano Arithmetic
- A Local Criterion for Polynomial-Time Stratified Computations
- Incompleteness in the finite domain
- Mining the surface: witnessing the low complexity theorems of arithmetic
- Approximate counting and NP search problems
- Characterising definable search problems in bounded arithmetic via proof notations
- Witnessing functions in bounded arithmetic and search problems
- Alternating minima and maxima, Nash equilibria and bounded arithmetic
- The provably total NP search problems of weak second order bounded arithmetic
- Witnessing flows in arithmetic
- Feasible functionals and intersection of ramified types
- Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem
- Title not available (Why is that?)
- Total search problems in bounded arithmetic and improved witnessing
- On Search Problems in Complexity Theory and in Logic (Abstract)
This page was built for publication: Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3583040)
