Abstract
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(.)).