Sparse sets in NP-P

1 January 1983

proceedings article
Published by Association for Computing Machinery (ACM)

p. 382-391
https://doi.org/10.1145/800061.808769

Abstract

This paper investigates the structural properties of sets in NP-P and shows that the computational difficulty of lower density sets in NP depends explicitly on the relations between higher deterministic and nondeterministic time-bounded complexity classes. The paper exploits the recently discovered upward separation method, which shows for example that there exist sparse sets in NP-Pif and only if EXPTIME @@@@ NEXPTIME. In addition, the paper uses relativization techniques to determine logical possibilities, limitations of these proof techniques, and, for the first time, to exhibit structural differences between relativized NP and CoNP.

Keywords

SPARSE SETS
LOGICAL POSSIBILITY
EXPTIME VERSUS NEXPTIME
STRUCTURAL DIFFERENCE
COMPUTATIONAL DIFFICULTY
LOWER DENSITY SET
SPARSE SET
PROOF TECHNIQUE
NONDETERMINISTIC TIME-BOUNDED COMPLEXITY CLASS
RELATIVIZATION TECHNIQUE
STRUCTURAL PROPERTY
RELATIVIZED NP
HIGHER DETERMINISTIC

This publication has 0 references indexed in Scilit: