3. L-Isomorphisms of Complete Sets
Society for Industrial and Applied Mathematics eBooks · 1989
In the previous section we saw that the families of languages NL,CSL,P,NPandPTAPE have complete problems and that many natural problems form complete problems for these families. In this section we will show that all the known complete sets for these families are, respectively, similar in a very strong technical sense. More precisely, we will show that all the known complete sets for the different classes are, respectively, L-isomorphic. This result implies that all the previously “known” complete sets in NP, PTAPE, etc. are p-isomorphic as was shown in [3], [4] and extends in a uniform way the L-isomorphism results to where the p-isomorphism results did not apply [21].