Name
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. The middle bit of f(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 Mod(k) P, k greater than or equal to 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 x(1),...,x(w) and output the [log(2)(w)/2]th hit in the binary representation of the number Sigma(i=1)(w) X(1) . Every language in ACC can be computed by a family of depth-2 deterministic circuits of size 2 O-(logn(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. (C) 1995 Academic Press, Inc. |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1006/jcss.1995.1036 | J. Comput. Syst. Sci. |
Keywords | Field | DocType |
polynomial time | Polynomial hierarchy,Discrete mathematics,Binary logarithm,Combinatorics,Circuit complexity,Upper and lower bounds,Turing machine,Time complexity,Mathematics,Binary number,Computational complexity theory | Journal |
Volume | Issue | ISSN |
50 | 3 | 0022-0000 |
Citations | PageRank | References |
28 | 1.18 | 28 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Frederic Green | 1 | 28 | 1.18 |
| Johannes Köbler | 2 | 580 | 46.51 |
| Kenneth W. Regan | 3 | 201 | 23.15 |
| Thomas Schwentick | 4 | 2373 | 155.10 |
| Jacobo Torán | 5 | 564 | 49.26 |