Number of the records: 1
Consequences of the Provability of $NP /subseteq P/poly$
- 1.0088021 - MÚ 2008 RIV US eng J - Journal Article
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
R&D Projects: GA AV ČR IAA1019401; GA ČR GA201/05/0124; GA MŠMT LC505
Institutional research plan: CEZ:AV0Z10190503
Keywords : computational complexity * proof complexity * bounded arithmetic
Subject RIV: BA - General Mathematics
Impact factor: 0.609, year: 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í.
Permanent Link: http://hdl.handle.net/11104/0149701
File Download Size Commentary Version Access Krajicek1.pdf 1 1.5 MB Publisher’s postprint require
Number of the records: 1