TR06-157 Authors: Lance Fortnow, Rahul Santhanam

Publication: 15th December 2006 20:07

Downloads: 3793

Keywords:

We explore whether various complexity classes can have linear or

more generally $n^k$-sized circuit families for some fixed $k$. We

show

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).