2014/08/27 by Sunny Daniels, Daniels, Sunny
Computer Science · #Computability, Logic, AI Algorithms #Logic, programming, and type systems #cs.CC #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1408.6334
This is a corrected version of my previous article (of the same name) which attracted the attention of Professor Lance Fortnow at Georgia Institute of Technology ("Sixteen Years in the Making" in his Complexity Theory Blog). The original had a missing closing bracket in a footnote and a reference to the wrong step in the machine for $Λ_k$
arxiv created 2014/09/17 · arxiv updated 2014/09/18
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 Σ2P that cannot be simulated by a family of logic circuits of size nk. 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 nk.