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.

In this paper we investigate the structure of sets which are complete for various classes. We show, for example, that sets complete for deterministic time classes contain infinite polynomial time recognizable subsets, thus showing that they are not complex almost everywhere. We show by a related technique that any set complete for NEXP_TIME contains an infinite subset in DEXP_TIME, thereby showing that these sets do not require the use of non-determinism almost everywhere. Furthermore, we show that complete sets for deterministic time classes have effective I.O. speed-up to a polynomial; this strengthens a result of Stockmeyer.

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.

In this note we show that the tape bounded complexity classes of languages over single letter alphabets are closed under complementation. We then use this result to show that there exists an infinite hierarchy of tape bounded complexity classes of sla languages between log n and log log n tape bounds. We also show that every infinite sla language recognizable on less than log n tape has infinitely many different regular subsets, and, therefore, the set of primes in unary notation, P, requires exactly log n tape for its recognition and every infinite subset of P requires at least log n tape.