All reports by Author Marcus Schaefer:

__
TR04-071
| 11th August 2004
__

Marcus Schaefer, Stephen A. Fenner#### Simplicity and Strong Reductions

Marcus Schaefer, Stephen A. Fenner

A set is called NP-simple if it lies in NP, and its complement is infinite, and does not contain any infinite subsets in NP. Hartmanis, Li and Yesha proved that no set which is hard for NP under many-one (Karp) reductions is NP-simple unless the intersection of NP and coNP ... more >>>