Portal de Periódicos da CAPES

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

1977; Society for Industrial and Applied Mathematics; Volume: 6; Issue: 2 Linguagem: Inglês

10.1137/0206023

1095-7111

L. Berman, Juris Hartmanis,

Algorithms and Data Compression

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 also relate the existence of sparse complete sets to the existence of simple combinatorial circuits for the corresponding truncated recognition problem of these languages.