1977/06/01 by L. Berman, Juris Hartmanis · 5 citations
Computer Science · Mathematics · #semigroups and automata theory #Algorithms and Data Compression #Machine Learning and Algorithms #Combinatorics #Mathematics #Alphabet #Simple (philosophy) #Time complexity #Context (archaeology) #Discrete mathematics #Regular language #NP-complete #Computer science #Theoretical computer science #Automaton
paper · doi:10.1137/0206023
openalex publication_date 1977/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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. 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.