Proof Systems that Take Advice

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Proof Systems that Take Advice

Popis výsledku v původním jazyce

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

Název v anglickém jazyce

Proof Systems that Take Advice

Popis výsledku anglicky

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

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2011

Kód důvěrnosti údajů

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

Název periodika

Information and Computation

ISSN

0890-5401

e-ISSN

—

Svazek periodika

209

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

13

Strana od-do

320-332

Kód UT WoS článku

000287382300005

EID výsledku v databázi Scopus

—