A taxonomy of complexity classes of functions

摘要

This paper comprises a systematic comparison of several complexity classes of functions that are computed nondeterministically in polynomial time or with an oracle in NP. There are three components to this work:•A taxonomy is presented that demonstrates all known inclusion relations of these classes. For (nearly) each inclusion that is not shown to hold, evidence is presented to indicate that the inclusion is false. As an example, consider FewPF, the class of multivalued functions that are nondeterministically computable in polynomial time such that for each x there is a polyomial bound on the number of distinct output values of f(x). We show that FewPF ⊆c PFNPtt. However, we show PFNPtt ⊆ FewPF if and only if NP = co-NP, and thus PFNPtt ⊆ FewPF is likely to be false.•Whereas it is known that PNP(O(log n)) = PNPtt ⊆ PNP, we show that PFNP(O(log n)) = PFNPtt implies P = FewP and R = NP. Also, we show that PFNPtt = PFNP if and only if PNPtt = PNP.•We show that if every nondeterministic polynomial-time multivalued function has a single-valued nondeterministic refinement (equivalently, if every honest function that is computable in polynomial-time can be inverted by a single-valued nondeterministic function), then there exists a disjoint pair of NP-complete sets such that every separator is NP-hard. The latter is a previously studied open problem that is closely related to investigations on promise problems. This result motivates a study of reductions between partial multivalued functions.