NP search problems in low fragments of bounded arithmetic
From MaRDI portal
Publication:5294030
DOI10.2178/jsl/1185803628zbMath1118.03051MaRDI QIDQ5294030
Alan Skelley, Neil Thapen, Jan Krajíček
Publication date: 9 July 2007
Published in: Journal of Symbolic Logic (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.307.765
Related Items
Unnamed Item, Approximate counting and NP search problems, Parity Games and Propositional Proofs, The NP Search Problems of Frege and Extended Frege Proofs, Mining the surface: witnessing the low complexity theorems of arithmetic, Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\), Nested PLS, A note on propositional proof complexity of some Ramsey-type statements, 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, Alternating minima and maxima, Nash equilibria and bounded arithmetic, Towards a unified complexity theory of total functions, Random resolution refutations, Typical forcings, NP search problems and an extension of a theorem of Riis, POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC, Examining Fragments of the Quantified Propositional Calculus, On the correspondence between arithmetic theories and propositional proof systems – a survey, A Characterisation of Definable NP Search Problems in Peano Arithmetic
Cites Work