Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR04-103 | 19th November 2004 00:00

NP with Small Advice

RSS-Feed




TR04-103
Authors: Lance Fortnow, Adam Klivans
Publication: 24th November 2004 18:45
Downloads: 3510
Keywords: 


Abstract:

We prove a new equivalence between the non-uniform and uniform complexity of exponential time. We show that EXP in NP/log if and only if EXP = P^NP|| (polynomial time with non-adaptive queries to SAT). Our equivalence makes use of a recent result due to Shaltiel and Umans showing EXP in P^NP|| implies EXP in NP/poly.



ISSN 1433-8092 | Imprint