On Isomorphisms and Density of $NP$ and Other Complete Sets

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...