Consequences of the provability of NP ⊆ P/poly
Consequences of the provability of NP ⊆ P/poly
复制标题
NP ⊆ P/poly 可证明性的后果
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
J. Krajícek
中科院分区：
文献类型：
--
作者：
S. Cook;J. Krajícek
Abstract We prove the following results: (i) PV proves NP ⊆ P/poly iff PV proves coNP ⊆ NP/O(1). (ii) If PV proves NP ⊆ P/poly then PV proves that the Polynomial Hierarchy collapses to the Boolean Hierarchy, (iii) proves NP ⊆ P/poly iff proves coNP ⊆ NP/O(log n). (iv) If proves NP ⊆ P/poly then proves that the Polynomial Hierarchy collapses to PNP[log n]. (v) If proves NP ⊆ P/poly then proves that the Polynomial Hierarchy collapses to PNP. Motivated by these results we introduce a new concept in proof complexity: proof systems with advice, and we make some initial observations about them.
