Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

Turing Machines with Few Accepting Computations and Low Sets for PP

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.

Ps-File: Turing Machines with Few Accepting Computations and Low Sets for PP