On Isomorphisms and Density of $NP$ and Other Complete Sets
Leonard Berman, Juris Hartmanis · SIAM Journal on Computing · 1977
If all $NP$ complete sets are isomorphic under deterministic polynomial time mappings (p-isomorphic) then $P e NP$ and if all PTAPE complete sets are P-isomorphic then $P e {\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 also relate the existence of sparse complete sets to the existence of simple combinatorial circuits for the corresponding truncated recognition problem of these languages.