Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with NP-simple:
TR04-071 | 11th August 2004
Marcus Schaefer, Stephen A. Fenner

Simplicity and Strong Reductions

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 >>>

ISSN 1433-8092 | Imprint