THE POWER OF THE MIDDLE BIT OF A P-FUNCTION

This paper studies the class MP of languages which can be solved in po lynomial time with the additional information of one bit from a #P fun ction f. The middle bit of f(x) is shown to be as powerful as any othe r bit, whereas the O(log n) bits at either end are apparently weaker. The polynomial hierarchy and the classes Mod(k) P, k greater than or e qual to 2, are shown to be low for MP. They are also low far a class w e call AmpMP which is defined by abstracting the ''amplification'' met hods of Toda (SIAM J, Comput. 20 ( 1991), 865-877). Consequences of th ese results for circuit complexity are obtained using the concept of a MidBit gate, which is defined to take binary inputs x(1),...,x(w) and output the [log(2)(w)/2]th hit in the binary representation of the nu mber Sigma(i=1)(w) X(1) . Every language in ACC can be computed by a f amily of depth-2 deterministic circuits of size 2 O-(logn(1)) With a M id Bit gate at the root and AND-gates of fan-in (log n)(O(1)) at the l eaves. This result improves the known upper bounds for the class ACC. (C) 1995 Academic Press, Inc.