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

High Sets for NP

Johannes Köbler and Uwe Schöning


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