Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

High Sets for NP

Johannes Köbler and Uwe Schöning

Abstract:

We consider sets that are high for the complexity class NP with respect to several operators on complexity classes. We review several other generalized NP-completeness and NP-hardness notions with respect to weak reducibilities and compare it to respective highness classes. The main contribution of this paper is a proof that NP-hard sets with respect to polynomial-size circuit reducibility are high for NP with respect to the operator ZPP(NP(.)).

Ps-File: High Sets for NP