A Characterisation of Definable NP Search Problems in Peano Arithmetic

DOI10.1007/978-3-642-02261-6_1zbMath1246.68119OpenAlexW122675930MaRDI QIDQ3638270

Arnold Beckmann

Publication date: 2 July 2009

Published in: Logic, Language, Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02261-6_1

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Approximate counting and NP search problems ⋮ Mining the surface: witnessing the low complexity theorems of arithmetic

Cites Work

• On the computational complexity of cut-reduction
• Proof theory. The first step into impredicativity
• How easy is local search?
• Structure and definability in general bounded arithmetic theories
• Finite investigations of transfinite derivations
• Ordinal notations and well-orderings in bounded arithmetic
• Notation systems for infinitary derivations
• The provably total search problems of bounded arithmetic
• Fragments of Bounded Arithmetic and Bounded Query Classes
• POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC
• An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
• NP search problems in low fragments of bounded arithmetic
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item