The provably total search problems of bounded arithmetic
From MaRDI portal
Publication:3018648
DOI10.1112/plms/pdq044zbMath1225.03081OpenAlexW2167477884MaRDI QIDQ3018648
Publication date: 27 July 2011
Published in: Proceedings of the London Mathematical Society (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1112/plms/pdq044
combinatorial principlesNP search problemsbounded arithmetic hierarchymultiparty communication protocolsreductions between gamesresolution lower bound
First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)
Related Items
The NP Search Problems of Frege and Extended Frege Proofs ⋮ Approximate counting and NP search problems ⋮ FRAGMENTS OF APPROXIMATE COUNTING ⋮ Typical forcings, NP search problems and an extension of a theorem of Riis ⋮ On the complexity of finding falsifying assignments for Herbrand disjunctions ⋮ Parity Games and Propositional Proofs ⋮ The limits of tractability in resolution-based propositional proof systems ⋮ Short refutations for an equivalence‐chain principle for constant‐depth formulas ⋮ A note on propositional proof complexity of some Ramsey-type statements ⋮ Mining the surface: witnessing the low complexity theorems of arithmetic ⋮ 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 ⋮ The canonical pairs of bounded depth Frege systems ⋮ INCOMPLETENESS IN THE FINITE DOMAIN ⋮ Towards a unified complexity theory of total functions ⋮ Improved witnessing and local improvement principles for second-order bounded arithmetic ⋮ A Characterisation of Definable NP Search Problems in Peano Arithmetic ⋮ Induction rules in bounded arithmetic ⋮ Random resolution refutations ⋮ Alternating minima and maxima, Nash equilibria and bounded arithmetic
