Limitations of the upward separation technique (preliminary version)

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

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].

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 16th International Colloquium, Proceedings
EditorsMariangiola Dezani-Ciancaglini, Simonetta Ronchi Della Rocca, Giorgio Ausiello
PublisherSpringer Verlag
Pages18-30
Number of pages13
ISBN (Print)9783540513711
DOIs
StatePublished - 1989
Event16th International Colloquium on Automata, Languages and Programming, 1989 - Stresa, Italy
Duration: Jul 11 1989Jul 15 1989

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume372 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other16th International Colloquium on Automata, Languages and Programming, 1989
Country/TerritoryItaly
CityStresa
Period7/11/897/15/89

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Limitations of the upward separation technique (preliminary version)'. Together they form a unique fingerprint.

Cite this