Show simple item record

dc.contributor.authorLandweber, Lawrenceen_US
dc.contributor.authorLipton, Richarden_US
dc.contributor.authorRobertson, Edwarden_US
dc.description.abstractA simple technique is developed for manipulating the relative complexity of sets with respect to polynomial time reducibility. One application is the definition of a minimal pair (with respect to polynomial time reducibility) of sets in NP-P. The last section proves that the NP-complete are effectively enumerable while NP-P is not.en_US
dc.publisherUniversity of Wisconsin-Madison Department of Computer Sciencesen_US
dc.titleOn the Structure of Sets in NP and Other Complexity Classesen_US
dc.typeTechnical Reporten_US

Files in this item


This item appears in the following Collection(s)

  • CS Technical Reports
    Technical Reports Archive for the Department of Computer Sciences at the University of Wisconsin-Madison

Show simple item record