The provably total search problems of bounded arithmetic

DOI10.1112/plms/pdq044zbMath1225.03081OpenAlexW2167477884MaRDI QIDQ3018648

Neil Thapen, Alan Skelley

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

zbMATH Keywords

combinatorial principlesNP search problemsbounded arithmetic hierarchymultiparty communication protocolsreductions between gamesresolution lower bound

Mathematics Subject Classification ID

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