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 @@@@ NP and if all PTAPE complete sets are p-isomorphic then P @@@@ PTAPE. We show that all NP complete sets known (in the literature) are indeed p-isomorphic and so are the known PTAPE complete sets. Thus showing that, inspite of the radically different origins and attempted simplification of these sets, all the known NP complete sets are identical but for polynomially time bounded permutations.

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.