On the Structure of Sets in NP and Other Complexity Classes

A simple technique is developed for manipulating the relative complexity of stes 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.

Download this report (PDF)

Return to tech report index