Počet záznamů: 1
Consequences of the Provability of $NP /subseteq P/poly$
- 1.0088021 - MÚ 2008 RIV US eng J - Článek v odborném periodiku
Cook, S. - Krajíček, Jan
Consequences of the Provability of $NP /subseteq P/poly$.
[Důsledky dokazatelnosti $NP /subseteq P /poly $.]
Journal of Symbolic Logic. Roč. 72, č. 4 (2007), s. 1353-1371. ISSN 0022-4812. E-ISSN 1943-5886
Grant CEP: GA AV ČR IAA1019401; GA ČR GA201/05/0124; GA MŠMT LC505
Výzkumný záměr: CEZ:AV0Z10190503
Klíčová slova: computational complexity * proof complexity * bounded arithmetic
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 0.609, rok: 2007
We derive several consequences of the provability of $NP/subseteq P/poly$ in various bounded arithmetic theories. We define the concept of a propositional proof system with advice.
Odvodíme několik důsledků dokazatelnosti $NP/subseteq P/ poly$ v různých teoriích omezené aritmetiky. Definujeme koncept výrokového důkazového systému s pomocí.
Trvalý link: http://hdl.handle.net/11104/0149701
Název souboru Staženo Velikost Komentář Verze Přístup Krajicek1.pdf 1 1.5 MB Vydavatelský postprint vyžádat
Počet záznamů: 1