Abstract
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.