A Characterisation of Definable NP Search Problems in Peano Arithmetic

DOI10.1007/978-3-642-02261-6_1MaRDI QIDQ3638270zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Characterising definable search problems in bounded arithmetic via proof notations
• NP search problems in low fragments of bounded arithmetic
• The provably total NP search problems of weak second order bounded arithmetic
• Herbrandizing search problems in Bounded Arithmetic
• Witnessing functions in bounded arithmetic and search problems

Cites work

• scientific article; zbMATH DE number 3912375 (Why is no real title available?)
• scientific article; zbMATH DE number 3497842 (Why is no real title available?)
• scientific article; zbMATH DE number 1088186 (Why is no real title available?)
• scientific article; zbMATH DE number 5038466 (Why is no real title available?)
• scientific article; zbMATH DE number 3271491 (Why is no real title available?)
• An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
• Characterising definable search problems in bounded arithmetic via proof notations
• Finite investigations of transfinite derivations
• Fragments of Bounded Arithmetic and Bounded Query Classes
• How easy is local search?
• NP search problems in low fragments of bounded arithmetic
• Notation systems for infinitary derivations
• On the computational complexity of cut-reduction
• Ordinal notations and well-orderings in bounded arithmetic
• Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic
• Proof theory. The first step into impredicativity
• Structure and definability in general bounded arithmetic theories
• The provably total search problems of bounded arithmetic

Cited in

(7)

• Nested PLS
• 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
• Arithmetical definability and computational complexity
• The provably total NP search problems of weak second order bounded arithmetic
• Witnessing flows in arithmetic

This page was built for publication: A Characterisation of Definable NP Search Problems in Peano Arithmetic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3638270)