A constructive proof presenting languages in $Σ_2^P$ that cannot be decided by circuit families of size $n^k$
Sunny Daniels · arXiv (Cornell University) · 2014
As far as I know, at the time that I originally devised this result (1998), this was the first constructive proof that, for any integer $k$, there is a language in $Σ_2^P$ that cannot be simulated by a family of logic circuits of size $n^k$. However, this result had previously been proved non-constructively: see Cai and Watanabe [CW08] for more information on the history of this problem. This constructive proof is based upon constructing a language $Γ$ derived from the satisfiabiility problem, and a language $Λ_k$ defined by an alternating Turing machine. We show that the union of $Γ$ and $Λ_k$ cannot be simulated by circuits of size $n^k$.