Fixed-Polynomial Size Circuit Bounds

We explore whether various complexity classes can have linear or more generally n k-sized circuit families for some fixed k. We show • The following are equivalent, – NP is in SIZE(nk) (has O(nk)-size circuit families) for some k is in SIZE(nk) for some k – P NP – 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. • For all k, MA is in SIZE(n k) if and only if AM is in SIZE(n k). • One cannot show ⊕P does not have n 2-size circuit families without using nonrelativizing techniques beyond those already used for similar results. • For every k, the class PPP does not have nk-sized circuits with Σ ⊕P k-gates. • For a large number of natural classes C and constant k, C is in SIZE(nk) if and only if C/1 ∩ P/poly is in SIZE(nk)