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