On the Power of One Bit of a P Function

We introduce the class MP of languages L which can be solved in polynomial time with an oracle that returns one bit of a #P function value f(x). That one bit suffices for any L in the polynomial hierarchy follows from the proof of S. Toda's theorem [Tod89, Tod91] that PH ` P #P , so PH ` BP[ \Phi P] ` C \Phi P ` MP ` P #P[1] : We show that the middle bit of f(x) is as powerful as any other bit, and that a wide range of bits around the middle have the same power. By contrast, the O(log n)-many least significant bits are equivalent to \Phi P [BGH90], and we show that the O(log n)-many most significant bits are equivalent to PP; hence these bits are probably weaker. MP is interesting because it is a natural complexity class with complete problems at a level where most of our current knowledge of counting classes and corresponding circuit-theory problems runs out. We study the subclass AmpMP of languages whose MP representations can be "amplified," showing that BP[ \Phi P] ` AmpMP, a..