On Sparse Sets in NP-P
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$.
computer science; technical report
Previously Published As