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

Johannes Köbler and Seinosuke Toda

Abstract:

We investigate the computational power of the new counting class ModP. We show that ModP is polynomial-time truth-table equivalent in power to #P and that ModP is contained in the class AmpMP.

As a consequence, the classes PP, ModP and AmpMP are all Turing equivalent, and thus AmpMP and ModP are not low for MP unless the counting hierarchy collapses to MP. Furthermore, we show that every set in C=P is reducible to some set in ModP via a random many-one reduction that uses only logarithmically many random bits. Hence, ModP and AmpMP are not closed under polynomial-time conjunctive reductions unless the counting hierarchy collapses.