Title :
NP with small advice
Author :
Fortnow, Lance ; Klivans, Adam R.
Author_Institution :
Dept. of Comput. Sci., Chicago Univ., IL, USA
Abstract :
We prove a new equivalence between the non-uniform and uniform complexity of exponential time. We show that EXP ⊆ NP/log if and only if EXP = P||NP Our equivalence makes use of a recent result due to Shaltiel and Umans showing EXP in P||NP implies EXP in NP/poly.
Keywords :
computational complexity; equivalence classes; NP problem; computational complexity; equivalence; exponential time; nonuniform complexity class; uniform complexity class; Circuits; Computational complexity; Computer science; Polynomials; Turing machines;
Conference_Titel :
Computational Complexity, 2005. Proceedings. Twentieth Annual IEEE Conference on
Print_ISBN :
0-7695-2364-1
DOI :
10.1109/CCC.2005.15
