Sparse sets in NP-P: EXPTIME versus NEXPTIME. (English) Zbl 0586.68042

Hartmanis, J.; Immerman, N.; Sewelson, V.

Inf. Control 65, 158-181 (1985).

A fascinating problem relating to the conjecture NP\(\neq P\) is the following: what are the structural properties of the sets in NP-P? And this question was a reason which led to the definition of the density of sets. A set has the density \(\delta\) (n) iff it contains only \(\delta\) (n) elements up to size n. A set is said to be sparse if it has a polynomial density. The paper under review investigates the structural properties of sets in NP-P, the relation between the nonexistence of sparse sets in NP-P and in other parts of the polynomial hierarchy, and shows that the computational complexity of lower density sets in NP depends explicitly on the relations between higher deterministic and nondeterministic time-bounded complexity classes.

Reviewer: D.Lucanu

MSC:

68Q25	Analysis of algorithms and problem complexity
03D15	Complexity of computation (including implicit computational complexity)

Keywords:

exponential time; structural properties of the sets in NP-P; density; lower density sets in NP; time-bounded complexity classes