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