The Power of the Middle Bit of a #P Function
Frederic Green, Johannes Köbler, Kenneth W. Regan, Thomas Schwentick,
and Jacobo Toran
Abstract:
This paper studies the class MP of languages which can be solved in
polynomial time with the additional information of one bit from a #P
function f. The middle bit of f(x) is shown to be as powerful as any
other bit, whereas the O(log n) bits at either end are apparently
weaker. The polynomial hierarchy and the classes ModkP are shown to be
low for MP. They are also low for a class we call AmpMP which is
defined by abstracting the "amplification" methods of Toda (SIAM J.
Comput. 20, 865--877, 1991).
Consequences of these results for circuit complexity are obtained
using the concept of a MidBit gate. Every language in ACC can be
computed by a family of depth-2 deterministic circuits of
quasi-polynomial size with a MidBit gate at the root and AND-gates of
poly-log fan-in at the leaves. This result improves the known upper
bounds for the class ACC.