Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > STRONG REDUCIBILITIES:
Reports tagged with strong reducibilities:
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