|
Published Articles >> Table of Contents >> Abstract
19th Annual IEEE Conference on Computational Complexity (CCC'04)
pp. 130-138
Separating Complexity Classes Using Structural Properties
Harry Buhrman, Centrum voor Wiskunde en Informatica
Leen Torenvliet, University of Amsterdam
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2004.1313820
Send link to a friend
| Abstract |
|
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.
|
 Additional Information
|
Citation:
Harry Buhrman, Leen Torenvliet,
"Separating Complexity Classes Using Structural Properties,"
ccc,
pp. 130-138,
19th Annual IEEE Conference on Computational Complexity (CCC'04),
2004
|
|
