Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR06-157 | 14th December 2006 00:00

Fixed-Polynomial Size Circuit Bounds


Authors: Lance Fortnow, Rahul Santhanam
Publication: 15th December 2006 20:07
Downloads: 2694


We explore whether various complexity classes can have linear or
more generally $n^k$-sized circuit families for some fixed $k$. We

1) The following are equivalent,
- NP is in SIZE(n^k) (has O(n^k)-size circuit families) for some k
- P^NP|| is in SIZE(n^k) for some k
- ONP/1 is in SIZE(n^k) for some k.
where ONP is the class of languages accepted by NP machines with some witness depending only on the input length.
2) For all k, MA is in SIZE(n^k) if and only if AM is in SIZE(n^k).
3) One cannot show Parity-P does not have
n^2-size circuit families without using nonrelativizing techniques
beyond those already used for similar results.
4) For every k, the class P^PP does not have n^k-sized circuits with Sigma_k^Parity-P-gates.
5) For a large number of natural classes C and constant k, C is in SIZE(n^k) if and only if C/1 \cap P/poly is in SIZE(n^k).

ISSN 1433-8092 | Imprint