摘要：We say that a first-order formula A(x1,…,xn) over R defines a Boolean function f:{0,1}n→{0,1}, if for every x1,…,xn∈{0,1}, A(x1,…,xn) is true iff f(x1,…,xn)=1. We show that:
(i) every f can be defined by a formula of size O(n),
(ii) if A is required to have at most k≥1 quantifier alternations, there exists an f which requires a formula of size 2Ω(n/k).
The latter result implies several previously known as well as some new lower bounds in computational complexity: a non-constructive version of the lower bound on span programs of Babai, Gál, and Wigderson (Combinatorica 1999); Rothvoß's result (CoRR 2011) that there exist 0/1 polytopes that require exponential-size linear extended formulations; a similar lower bound by Briët et al. (Math. Program. 2015) on semidefinite extended formulations; and a new result stating that a random Boolean function has exponential linear separation complexity. We note that (i) holds over any field of characteristic zero, and (ii) holds over any real closed or algebraically closed field.
