Three results on the polynomial isomorphism of complete sets
- 1 October 1986
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
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.Keywords
This publication has 6 references indexed in Scilit:
- A note on one-way functions and polynomial-time isomorphismsPublished by Association for Computing Machinery (ACM) ,1986
- Some remarks on witness functions for nonpolynomial and noncomplete sets in NPTheoretical Computer Science, 1985
- Sparse Sets in : RelativizationsSIAM Journal on Computing, 1985
- Generalized Kolmogorov complexity and the structure of feasible computationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- On Isomorphisms and Density of $NP$ and Other Complete SetsSIAM Journal on Computing, 1977
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ QuestionSIAM Journal on Computing, 1975