We study the robustness of complete sets for various complexity classes. A complete set A is robust if for any f(n)-dense set S ∊ P, A - S is still complete, where f(n) ranges from log(n), polynomial, to subexponential. We show that robustness can be used to separate complexity classes:
for every \le _m^p-complete set A for EXP and any subexponential dense sets S ∊ P, A - S is still Turing complete and under a reasonable hardness assumption even \le _m^p-complete. For EXP and the delta levels of the exponential hierarchy we show that for every Turing complete set A and any log-dense set S ∊ P, A - S is still Turing complete. There exists a 3-truth-table complete set A for EEXPSPACE, and a log-dense set S ∊ P such that A - S is not Turing complete. This implies that settling this issue for EEXP will either separate P from PSPACE or PH from EXP. We show that the robustness results for EXP and the delta levels of the exponential hierarchy do not relativize.
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb