THREE RESULTS ON THE POLYNOMIAL ISOMORPHISM OF COMPLETE SETS.

Judy Goldsmith, Deborah Joseph

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
Pages390-397
Number of pages8
DOIs
StatePublished - 1986

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

ASJC Scopus subject areas

  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'THREE RESULTS ON THE POLYNOMIAL ISOMORPHISM OF COMPLETE SETS.'. Together they form a unique fingerprint.

Cite this