TY - GEN
T1 - THREE RESULTS ON THE POLYNOMIAL ISOMORPHISM OF COMPLETE SETS.
AU - Goldsmith, Judy
AU - Joseph, Deborah
PY - 1986
Y1 - 1986
N2 - The authors prove three results that give some insight into why resolving the p-isomorphism question is so difficult for NP-complete sets. In particular, they show that there are relativized complexity classes in which all complete sets are isomorphic, and there are deterministic-time classes in which not all complete sets are isomorphic.
AB - The authors prove three results that give some insight into why resolving the p-isomorphism question is so difficult for NP-complete sets. In particular, they show that there are relativized complexity classes in which all complete sets are isomorphic, and there are deterministic-time classes in which not all complete sets are isomorphic.
UR - http://www.scopus.com/inward/record.url?scp=0022910675&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0022910675&partnerID=8YFLogxK
U2 - 10.1109/sfcs.1986.56
DO - 10.1109/sfcs.1986.56
M3 - Conference contribution
AN - SCOPUS:0022910675
SN - 0818607408
SN - 9780818607400
T3 - Annual Symposium on Foundations of Computer Science (Proceedings)
SP - 390
EP - 397
BT - Annual Symposium on Foundations of Computer Science (Proceedings)
ER -