Proof Systems that Take Advice

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F11%3A10106381" target="_blank" >RIV/00216208:11320/11:10106381 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1016/j.ic.2010.11.006" target="_blank" >http://dx.doi.org/10.1016/j.ic.2010.11.006</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.ic.2010.11.006" target="_blank" >10.1016/j.ic.2010.11.006</a>

Result language
angličtina
Original language name
Proof Systems that Take Advice
Original language description
One of the starting points of propositional proof complexity is the seminal paper by Cook and Reckhow [13], where they de?ned propositional proof systems as poly-time computable functions which have all propositional tautologies as their range. Motivatedby provability consequences in bounded arithmetic, Cook and Krajicek [12] have recently started the investigation of proof systems which are computed by poly-time functions using advice. In this paper we concentrate on three fundamental questions regarding this new model. First, we investigate whether a given language L admits a polynomially bounded proof system with advice. Depending on the complexity of the underlying language L and the amount and type of the advice used by the proof system, we obtain di?erent characterizations for this problem. In particular, we show that this question is tightly linked with the question whether L has small nondeterministic instance complexity. The second question concerns the existence of optimal p
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
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

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)