loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
19th Annual IEEE Conference on Computational Complexity (CCC'04)
Separating Complexity Classes Using Structural Properties
Amherst, Massachusetts
June 21-June 24
ISBN: 0-7695-2120-7
ASCII Text
x 
 
Harry Buhrman, Leen Torenvliet, "Separating Complexity Classes Using Structural Properties," Computational Complexity, Annual IEEE Conference on, pp. 130-138, 19th Annual IEEE Conference on Computational Complexity (CCC'04), 2004.
 
 
BibTex
x
 
@article{ 10.1109/CCC.2004.1313820,
author = {Harry Buhrman and Leen Torenvliet},
title = {Separating Complexity Classes Using Structural Properties},
journal ={Computational Complexity, Annual IEEE Conference on},
volume = {0},
year = {2004},
issn = {1093-0159},
pages = {130-138},
doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2004.1313820},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Computational Complexity, Annual IEEE Conference on
TI - Separating Complexity Classes Using Structural Properties
SN - 1093-0159
SP130
EP138
A1 - Harry Buhrman,
A1 - Leen Torenvliet,
PY - 2004
KW - null
VL - 0
JA - Computational Complexity, Annual IEEE Conference on
ER -
 
Harry Buhrman, Centrum voor Wiskunde en Informatica
Leen Torenvliet, University of Amsterdam

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.

    • 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
    Usage of this product signifies your acceptance of the Terms of Use.