On the power of generalized MOD-classes
FakultätenFakultät für Ingenieurwissenschaften und Informatik
LizenzStandard (Fassung vom 01.10.2008)
We investigate the computational power of the new counting class ModP which generalizes the classes ModpP, p prime. 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.
Erstellung / Fertigstellung