Characterising definable search problems in bounded arithmetic via proof notations

MaRDI QIDQ3081638zbMATH OpenFDO

Authors Arnold Beckmann, Samuel R. Buss

Publication date 9 March 2011

Mathematics Subject Classification ID

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

Recommendations

• Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic
• NP search problems in low fragments of bounded arithmetic
• Witnessing functions in bounded arithmetic and search problems
• Herbrandizing search problems in Bounded Arithmetic
• A Characterisation of Definable NP Search Problems in Peano Arithmetic

Cited in

(14)

• The provably total search problems of bounded arithmetic
• Herbrandizing search problems in Bounded Arithmetic
• Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic
• A Characterisation of Definable NP Search Problems in Peano Arithmetic
• Witnessing functions in bounded arithmetic and search problems
• An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
• Incompleteness in the finite domain
• Approximate counting and NP search problems
• Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\)
• Nested PLS
• Improved witnessing and local improvement principles for second-order bounded arithmetic
• Mining the surface: witnessing the low complexity theorems of arithmetic
• Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem
• Witnessing flows in arithmetic

This page was built for publication: Characterising definable search problems in bounded arithmetic via proof notations

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