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.