TY - GEN

T1 - Limitations of the upward separation technique (preliminary version)

AU - Allender, Eric

N1 - Funding Information:
1 Supported in part by National Science Foundation Research Initiation Grant number CCR-8810467.
Publisher Copyright:
© 1989, Springer-Verlag.

PY - 1989

Y1 - 1989

N2 - The upward separation technique was developed by Hartmanis, who used it to show that E=NE iff there is no sparse set in NP-P [Ha-83a]. This paper shows some inherent limitations of the technique. The main result of this paper is the construction of an oracle relative to which there are extremely sparse sets in NP-P, but NEE = EE; this is in contradiction to a result claimed in [Ha-83, HIS-85]. Thus, although the upward separation technique is useful in relating the existence of sets of polynomial (and greater) density in NP-P to the NTIME(T(n)) = DTIME(T(n)) problem, the existence of sets of very low density in NP-P can not be shown to have any bearing on this problem until proof techniques are developed which do not relativize. The oracle construction is also of interest since it is the first example of an oracle relative to which EE = NEE and E ≠ NE. (The techniques of [BWX-82], [Ku-85], and [Li-87] do not suffice to construct such an oracle.) The construction is novel and the techniques may be useful in other settings. In addition, this paper also presents a number of new applications of the upward separation technique, including some new generalizations of the original result of [Ha-83a].

AB - The upward separation technique was developed by Hartmanis, who used it to show that E=NE iff there is no sparse set in NP-P [Ha-83a]. This paper shows some inherent limitations of the technique. The main result of this paper is the construction of an oracle relative to which there are extremely sparse sets in NP-P, but NEE = EE; this is in contradiction to a result claimed in [Ha-83, HIS-85]. Thus, although the upward separation technique is useful in relating the existence of sets of polynomial (and greater) density in NP-P to the NTIME(T(n)) = DTIME(T(n)) problem, the existence of sets of very low density in NP-P can not be shown to have any bearing on this problem until proof techniques are developed which do not relativize. The oracle construction is also of interest since it is the first example of an oracle relative to which EE = NEE and E ≠ NE. (The techniques of [BWX-82], [Ku-85], and [Li-87] do not suffice to construct such an oracle.) The construction is novel and the techniques may be useful in other settings. In addition, this paper also presents a number of new applications of the upward separation technique, including some new generalizations of the original result of [Ha-83a].

UR - http://www.scopus.com/inward/record.url?scp=85027634682&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85027634682&partnerID=8YFLogxK

U2 - 10.1007/BFb0035749

DO - 10.1007/BFb0035749

M3 - Conference contribution

AN - SCOPUS:85027634682

SN - 9783540513711

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 18

EP - 30

BT - Automata, Languages and Programming - 16th International Colloquium, Proceedings

A2 - Dezani-Ciancaglini, Mariangiola

A2 - Della Rocca, Simonetta Ronchi

A2 - Ausiello, Giorgio

PB - Springer Verlag

T2 - 16th International Colloquium on Automata, Languages and Programming, 1989

Y2 - 11 July 1989 through 15 July 1989

ER -