On the Structure of Sets in NP and Other Complexity Classes

Simple item page
dc.contributor.authorLandweber, Lawrenceen_US
dc.contributor.authorLipton, Richarden_US
dc.contributor.authorRobertson, Edwarden_US
dc.date.accessioned2012-03-15T16:29:20Z
dc.date.available2012-03-15T16:29:20Z
dc.date.created1978en_US
dc.date.issued1978
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.format.mimetypeapplication/pdfen_US
dc.identifier.citationTR342
dc.identifier.urihttp://digital.library.wisc.edu/1793/58126
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

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
TR342.pdf
Size:
2.36 MB
Format:
Adobe Portable Document Format
Download

Collections

CS Technical Reports