A constructive proof presenting languages in Σ₂ᵖ that cannot be decided by circuit families of size nᵏ

الأصل · EN

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 Σ₂ᵖ that cannot be simulated by a family of logic circuits of size nᵏ. 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 Λₖ defined by an alternating Turing machine. We show that the union of Γ and Λₖ cannot be simulated by circuits of size nᵏ.