The provably total search problems of bounded arithmetic

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F11%3A00369680" target="_blank" >RIV/67985840:_____/11:00369680 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1112/plms/pdq044" target="_blank" >http://dx.doi.org/10.1112/plms/pdq044</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1112/plms/pdq044" target="_blank" >10.1112/plms/pdq044</a>

Result language
angličtina
Original language name
The provably total search problems of bounded arithmetic
Original language description
We give combinatorial principles GI(k), based on k-turn games, which are complete for the class of NP search problems provably total at the kth level T(2)(k) of the bounded arithmetic hierarchy and hence characterize the for all Sigma(b)(1) consequencesof T(2)(k). Our argument uses a translation of first-order proofs into large, uniform propositional proofs in a system in which the soundness of the rules can be witnessed by polynomial time reductions between games. We show that for all(Sigma) over cap(b)(1)(alpha) conservativity of T(2)(i+1) (alpha) over T(2)(i)(alpha) already implies. for all(Sigma) over cap (b)(1)(a) conservativity of T(2)(alpha) over T(2)(i)(alpha). We translate this into propositional form and give a polylogarithmic width CNF (GI(3)) over bar such that if (GI(3)) over bar has small R(log) refutations then so does any polylogarithmic width CNF which has small constant depth refutations. We prove a resolution lower bound for (GI(3)) over bar.
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
<a href="/en/project/LC505" target="_blank" >LC505: Eduard Čech Center for Algebra and Geometry</a><br>
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2011
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)