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
Artikelaktionen
zuletzt geändert: 24.03.09 WI
Benutzerspezifische Werkzeuge