The power of the middle bit
- 2 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 111-117
- https://doi.org/10.1109/sct.1992.215386
Abstract
The class of languages that can be recognized in polynomial time with the additional information of one bit from a P function is studied. In particular, it is shown that every Mod/sub k/P class and every class contained in PH are low for this class. These results are translated to the area of circuit complexity using MidBit (middle bit) gates. It is shown that every language in ACC can be computed by a family of depth-2 deterministic circuits of size 2 to the (log n)/sup c/ power with a MidBit gate at the root and AND-gates of fan-in (log n)/sup c/ at the leaves. This result improves the known upper bounds for the class ACC.Keywords
This publication has 17 references indexed in Scilit:
- Two remarks on the power of countingPublished by Springer Nature ,2005
- ON ACC and threshold circuitsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Bounded-width polynomial-size branching programs recognize exactly those languages in NC1Journal of Computer and System Sciences, 1989
- On the computational power of PP and (+)PPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- An oracle characterization of the counting hierarchyPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- The complexity of combinatorial problems with succinct input representationActa Informatica, 1986
- NP is as easy as detecting unique solutionsTheoretical Computer Science, 1986
- A low and a high hierarchy within NPJournal of Computer and System Sciences, 1983
- The complexity of computing the permanentTheoretical Computer Science, 1979
- Computational Complexity of Probabilistic Turing MachinesSIAM Journal on Computing, 1977