On sparse sets in NP–P |
| |
| Authors: | Juris Hartmanis |
| |
| Affiliation: | Department of Computer Science, 424 Upson Hall, Cornell University, Ithaca, NY 14853, USA |
| |
| Abstract: | The main result of this note shows that there exists a sparse set in NP that is not in P if and only if EXPTIME≠NEXPTIME. 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. |
| |
| Keywords: | Deterministic and nondeterministic computations P NP sparse sets |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
