Three results on the polynomial isomorphism of complete sets

Abstract

This paper proves three results relating to the isomorphism question for NP-complete sets. Result 1: We construct an oracle A such that SATA is ≤mP- complete for NPA and all ≤mP-complete sets for NPA are pA- isomorphic to SATA. Result 2: We construct a time function T(n) such that DTIME(T(n)) contains btt-complete sets, which are many-one equivalent, but are not p-isomorphic. The proof of this result has two corollaries: 1) There is an oracle, D, such that NPD contains non-p-isomorophic ≤m(D),P-complete sets. 2) There is a ≤mP-degree that contains non-p-isomorphic sets. Result 3: We show that no simple modification of the diagonalization argument used by Ko, Long and Du can be used to produce sets that are both EXPtime-complete w.r.t, polynomial many-one reducibility and not p-isomorphic.