Abstract
Johannes Köbler, Uwe Schöning, Seinosuke Toda, and Jacobo Toran
Abstract:
In this paper we study two different ways to restrict the power of NP:
We consider the class FewP of languages accepted by nondeterministic
polynomial time machines with a small number of accepting paths, and
also investigate subclasses of NP that are low for complexity classes
not known to be in the polynomial time hierarchy. We prove that Few
is low for the complexity classes PP, C=P, and parity-P. Furthermore,
it is shown that all sparse sets in NP, as well as the sets in the
probabilistic class BPP are PP-low. Finally, the lowness results are
used to obtain various positive relativization results.