The power of the middle bit of a #p function

fg This paper studies the class MP of languages which can be solved in poly nomial time with the additional information of one bit from a P function f The middle bit of fx is shown to be as powerful as any other bit whereas the Ologn bits at either end are apparently weaker The polynomial hierarchy and the classes Mod k P k are shown to be low for MP They are also low for a class we call AmpMP which is de ned by abstracting the ampli cation methods of Toda SIAM J Comput Consequences of these results for circuit complexity are obtained using the concept of a Mid Bit gate which is de ned to take binary inputs x x w and output the blog wc th bit in the binary representation of the number P