Separating Complexity Classes Using Structural Properties

Amherst, Massachusetts June 21-June 24

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/CCC.2004.1313820

19th Annual IEEE Conference on Comput ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Harry Buhrman Articles by Leen Torenvliet

	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

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.