Computer Science

The Power of the Middle Bit of a #P Function

Document Type

Article

Abstract

This paper studies the class MP of languages which can be solved in polynomial time with the additional information of one bit from a #P function f{hook}. The middle bit of f{hook}(x) is shown to be as powerful as any other bit, whereas the O(log n) bits at either end are apparently weaker. The polynomial hierarchy and the classes Modk P, k ≥ 2, are shown to be low for MP. They are also low far a class we call AmpMP which is defined by abstracting the "amplification" methods of Toda (SIAM J, Comput.20 ( 1991), 865-877). Consequences of these results for circuit complexity are obtained using the concept of a MidBit gate, which is defined to take binary inputs x1, ...,xw and output the ⌊log2(w)/2⌋th hit in the binary representation of the number Σwi=1xi . Every language in ACC can be computed by a family of depth-2 deterministic circuits of size 2log nO(1) with a Mid Bit gate at the root and AND-gates of fan-in (log n)O(1) at the leaves. This result improves the known upper bounds for the class ACC. © 1995 Academic Press. All rights reserved.

Publication Title

Journal of Computer and System Sciences

Publication Date

1995

Volume

50

Issue

3

First Page

456

Last Page

467

ISSN

0022-0000

DOI

10.1006/jcss.1995.1036

APA Citation

Green, F., Kobler, J., Regan, K. W., Schwentick, T., & Torán, J. (1995). The power of the middle bit of a# P function. Journal of Computer and System Sciences, 50(3), 456-467.

Link to Full Text

Share

COinS