On Isomorphisms and Density of $NP$ and Other Complete Sets
| Autor: | Leonard Berman, Juris Hartmanis |
|---|---|
| Rok vydání: | 1977 |
| Předmět: | |
| Zdroj: | STOC |
| ISSN: | 1095-7111 0097-5397 |
| DOI: | 10.1137/0206023 |
| Popis: | If all $NP$ complete sets are isomorphic under deterministic polynomial time mappings (p-isomorphic) then $P \ne NP$ and if all PTAPE complete sets are P-isomorphic then $P \ne {\text{PTAPE}}$. We show that all $NP$ complete sets known (in the literature) are indeed p-isomorphic and so are the known PTAPE complete sets. This shows that, in spite of the radically different origins and attempted simplification of these sets, all the known $NP$ complete sets are identical but for simple isomorphic codings computable in deterministic polynomial time.Furthermore, if all $NP$ complete sets are p-isomorphic then they all must have similar densities and, for example, no language over a single letter alphabet can be $NP$ complete, nor can any sparse language over an arbitrary alphabet be $NP$ complete. We show that complete sets in EXPTIME and EXPTAPE cannot be sparse and therefore they cannot be over a single letter alphabet. Similarly, we show that the hardest context-sensitive languages cannot be sparse. We als... |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|