On Sparse Sets in NP-P
Permanent Link(s)
Collections
Author
Hartmanis, Juris
Abstract
The main result of this note shows that there exist sparse sets in $NP$ that are not in $P$ if and only if NEXPTIME differs from EXPTIME. Several other results are derived about the complexity of very sparse sets in $NP-P$ and an interpretation of the meaning of these results is given in terms of the complexity of solving "individual instances" of problems in $NP-P$.
Date Issued
1982-08
Publisher
Cornell University
Keywords
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR82-508
Type
technical report