Fixed-Polynomial Size Circuit Bounds
Lance Fortnow, Rahul Santhanam, Ryan Williams · 2009
In 1982, Kannan showed that SigmaP2does not have nk-sized circuits for any k. Do smaller classes also admit such circuit lower bounds? Despite several improvements of Kannan's result, we still cannot prove that PNPdoes not have linear size circuits. Work of Aaronson and Wigderson provides strong evidence - the "algebrization'' barrier - that current techniques have inherent limitations in this respect. We explore questions about fixed-polynomial size circuit lower bounds around and beyond the algebrization barrier. We find several connections, including 1) The following are equivalent: -NP is in SIZE(nk) (has O(nk)-size circuit families) for some k -For each c, PNP[nc]is in SIZE(nk) for some k -ONP/1 is in SIZE(nk) for some k, where ONP is the class of languages accepted obliviously by NP machines, with witnesses for "yes" instances depending only on the input length. 2) For a large number of natural classes C and all k ges C is in SIZE(nk) if and only if C/1 cap P/poly is in SIZE(nk). 3) If there is a d such that MATIME(n) sube NTIME(nd), then PNPdoes not have O(nk) size circuits for any k > 0. 4) One cannot show n2-size circuit lower bounds for oplusP without new nonrelativizing techniques. In particular, the proof that PP nsube SIZE(nk) for all k relies on the (relativizing) result that PPPsube MA rArr PP nsube SIZE(nk), and we give an oracle relative to which PoplusPsube MA and oplusP sube SIZE(n2) both hold.