The power of the middle bit
FacultiesFakultät für Ingenieurwissenschaften und Informatik
We study the class of languages that can be recognized in polynomial time with the additional information of one bit from a #P function. In particular we show that every MOD~c class and every class contained in PH are low for this class. We translate these results to the area of circuit complexity using MidBit (middle bit) gates. AMidBitgate over w inputs x1 , ... ,xw is a gate which outputs the value of the Llog(w)/2Jth bit in the binary representation of the number E~1 Xi. We show that every language in ACC can be computed by a family of depth-2 deterministic circuits of size 2(logn)e with a MidBit gate at the root and AND-gates of fanin (log n )c at the leaves. This result improves the known upper bounds for the class ACC.
Subject HeadingsKomplexitätsklasse [GND]
Computational complexity [LCSH]