The power of the middle bit of a #P function
FakultätenFakultät für Ingenieurwissenschaften und Informatik
LizenzStandard (Fassung vom 01.10.2008)
We study the class of languages which can be solved in polynomial time with the additional information of one bit from a #P function. In particular we show that the polynomial hierarchy and the classes ModkP are low for this class. We translate these results to the area of circuit complexity using the concept of a MidBit gate, which is defined to take binary inputs x_1,...,x_n and output the middle bit in the binary representation of the sum over the inputs. We show that 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-logarithmic fan-in at the leaves. This result improves the known upper bounds for the class ACC.
Erstellung / Fertigstellung