Authors Pavel Hrube{\v{s}},
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 16 (9), 2020, pp. 1–12
www.theoryofcomputing.org
On the Complexity of Computing a
Random Boolean Function Over the Reals
Pavel Hrubeš∗
Received January 26, 2019; Revised July 10, 2020; Published October 21, 2020
Abstract. 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: the nonconstructive 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.
ACM Classification: F.1.3, F.2.3
AMS Classification: 68Q17, 03C10
Key words and phrases: complexity theory, lower bounds, average case, formula complexity, random
Boolean function, quantifier elimination
∗ Supported by GACR grant 19-05497S.
© 2020 Pavel Hrubeš
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2020.v016.a009
PAVEL H RUBE Š
1 Introduction
In computational complexity, we are typically interested in computing a Boolean function f : {0, 1}n →
{0, 1}. The central computational model is a Boolean circuit which computes the function by means
of the elementary operations ∧, ∨, ¬. The major open problem is to prove super-polynomial (or even
super-linear) lower bounds on the circuit size of an explicit function f . On the other hand, it is easy
to prove, non-constructively, that hard Boolean functions exist: comparing the number of circuits of a
given size with the total number of functions, there must exist Boolean functions which require circuits
of exponential size.
The counting argument relies on the fact that the elementary operations used are functions over a
small finite set. In the complexity literature, we also encounter algebraic models of computation which
do not have this property. While we are still interested in computing a Boolean function, we are allowed
to use intermediate operations over an infinite domain—typically the real numbers or some other infinite
field. To give a simple example: suppose we want to obtain f by computing a real polynomial g by means
of an arithmetic circuit (see [20, 11] for details) such that f (x) = g(x) holds over x ∈ {0, 1}n . Since
an arithmetic circuit can use arbitrary real numbers as constants, we can no longer apply the counting
argument in this case. A similar phenomenon occurs in the case of span programs [13, 2], and others.
A well-known strategy is to replace the counting argument with Warren’s theorem [22], or some
variant of it [17, 1] (see also Section 5). Warren’s theorem tells us how many sign-patterns can be achieved
in the image of a polynomial map, which is quite enough to prove the existence of hard functions in the
aforementioned models [11, 2, 17]. There is, however, at least one instance where this tool is apparently
insufficient. Suppose we want to compute f by means of a parametrized linear program as follows. We
have a system L(x, y) of linear inequalities over R in the variables x = hx1 , . . . , xn i and y = hy1 , . . . , ym i.
We require that for every x ∈ {0, 1}n , f (x) = 1 iff the system L(x, y) has a solution y ∈ Rm . Is there
a function f such that f requires an exponential number of inequalities to be defined this way? This
measure, which we call linear separation complexity, has been considered at least in [23, 15] and arises
in the context of the so-called extension complexity of polytopes (see Section 3 for details). The author
does not know how to resolve this question directly using Warren’s theorem. Nor does he know how to
extend the closely related result of Rothvoß [18] to this situation.
We can view these algebraic models a bit more abstractly. Consider a Boolean function defined by a
first-order formula A(x1 , . . . , xn ) over the reals. The function accepts on x1 , . . . , xn ∈ {0, 1} iff A(x1 , . . . , xn )
is true. Here, the formula A may contain constant symbols representing arbitrary real numbers as well
as quantifiers over R. In all the above examples, we are in fact defining f in terms of an existentially
quantified formula over the reals. Are there functions which are hard for this model? As we will see, this
depends on whether we bound the quantifier complexity of A. First, if no restriction is imposed, then
every Boolean function can be defined by a linear-size formula. Second, if A is required to have at most
k ≥ 1 quantifier alternations in the prenex form then there is a Boolean function requiring a formula of
size 2Ω(n/k) . The latter implies an exponential lower bound on the linear separation complexity as well
as the other models discussed. Our first result is achieved by a direct construction, the second one is a
corollary of known results on quantifier elimination over the reals. In this respect, our question is closely
related to the problem whether PR = NPR in the real Turing machine model (see [4] and [14] for survey).
We will see that both results hold in greater generality, in other fields besides the reals.
T HEORY OF C OMPUTING, Volume 16 (9), 2020, pp. 1–12 2
O N THE C OMPLEXITY OF C OMPUTING A R ANDOM B OOLEAN F UNCTION OVER THE R EALS
2 Preliminaries
Let F be a field. An F-formula, or simply a formula, is a first-order formula built from the function
and predicate symbols +, ×, = constant symbols ca for every element a of the field, as well as the usual
logical symbols (variables, Boolean connectives, and quantifiers ∃, ∀). If F is an ordered field, we allow
also the predicate symbols <, ≤ representing the ordering.1 We define the size of a formula as the number
of symbols in the formula (constants and variables having a unit cost). Every formula with no free
variables is either true or false, under the intended interpretation of symbols as operations over F.
Every quantifier-free formula over a field is of the form B(t1 = t10 , . . . ,tm = tm0 ), where B is a propo-
sitional formula defining a Boolean function and ti ,ti0 are terms defining polynomials with coefficients
from F. Over an ordered field, we may also encounter the atomic formulas ti < ti0 , ti ≤ ti0 . We will
take the liberty to identify the constant ca with a and, occasionally, identify terms with the polynomials
they represent. A Σ1 -formula is a formula of the form ∃x1 . . . ∃xn A, where A is quantifier-free (a. k. a.
Σ0 -formula). Similarly, a Σ2 -formula is of the form ∃x1 . . . ∃xn ∀y1 . . . ∀ym A, and so on: a Σk+2 -formula
is of the form ∃x1 . . . ∃xn ∀y1 . . . ∀ym A with A being Σk . Every formula can be converted to an equivalent
Σk -formula of nearly the same size, for some k. One could also define Πk -formulas, but we have no need
for that.
Let F be a field or an ordered field. Let A(x1 , . . . , xn ) be an F-formula with no free variables other
than x1 , . . . , xn . We will say that A defines a Boolean function f : {0, 1}n → {0, 1} if the following holds:
f (σ1 , . . . , σn ) = 1 iff A(σ1 , . . . , σn ) is true, for every σ1 , . . . , σn ∈ {0, 1} .
In Sections 4 and 5, we will prove the following main results:
Theorem 2.1. Let F be a field of characteristic zero. Given an n-variate Boolean function f and 1 ≤ k ≤ n,
f can be defined by a Σ2k−1 -formula of size O(k2n/k ).
Theorem 2.2. Let F be either a real closed field or an algebraically closed field. Then for every k > 0
and n, there exists a Boolean function f in n variables such that every Σk -formula defining f must have
size at least 2Ω(n/k) .
Setting k = n, Theorem 2.1 implies that every n-variate Boolean function can be defined by a formula
of linear size. We emphasize that Theorem 2.1 is possible, and Theorem 2.2 is non-trivial, only due to the
fact that we allow arbitrary constants from F to appear in the formula defining f . Let us also note that
Theorem 2.2 requires some assumption on the underlying field. Remarkably, it is false over the field of
rationals.
Observation 2.3. Over Q (as an unordered field), every Boolean function in n variables can be defined
by a Σ4 -formula of size O(n).
Proof sketch. This relies on a beautiful result of Julia Robinson [16] who showed that integers can be
defined inside Q by a single first-order formula. The same applies to non-negative integers. Working over
N, a Boolean function can be defined by a Σ1 -formula of linear size. This is because the truth-table of f
1 The potential error resulting from forgetting the order in a real closed field would be small: x ≤ y can be defined as
∃u(y = x + u2 ).
T HEORY OF C OMPUTING, Volume 16 (9), 2020, pp. 1–12 3
PAVEL H RUBE Š
can be encoded by a single natural number from which values of f can be recovered by a Σ1 -formula—cf.,
the proof of Theorem 4.2. This gives a linear-size Σk -formula over Q for some fixed k. The more accurate
bound k = 4 is achieved by inspecting the quantifier complexity of Robinson’s formula.
The power of Σ1 -formulas
We note that already the class of Σ1 -formulas is quite robust. That is, many syntactic restrictions or
relaxations of the definition lead essentially to the same class. Recall that a Σ1 -formula is of the form
∃y∈Fr B(t1 = t10 , . . . ,tm = tm0 ), where B is a Boolean formula and ti ,ti0 are terms. The latter can be seen as
the so-called arithmetic formulas defining polynomials over F. Note that if we allow B to be a Boolean
circuit instead, we do not get a stronger model: introducing new variables representing the gates of the
circuit we can rewrite B as a Σ1 -formula of a linear size. The same applies if we allow the terms ti ,ti0 to
be computed by arithmetic circuits. In fact, all polynomial-time computations in the sense of [4] can
be expressed as small Σ1 -formulas. In turn, every Σ1 -formula A(x1 , . . . , xn ) of size s can equivalently be
written as ∃y1 . . . ∃ym (h1 = 0 ∧ · · · ∧ ht = 0), where m,t ≤ O(s), and h1 , . . . , ht are polynomials of degree
two. This is true both in an ordered and an unordered field. In the ordered case, this can furthermore be
written as ∃y1 . . . ∃ym (h = 0), where h is a single polynomial of degree four. That is, the complexity of a
Σ1 -formula can be captured as the number of bound variables in an expression involving only low-degree
polynomials. This allows us to redefine Σ1 -complexity in a mathematically cleaner way.
3 An application: extension and separation complexity
As mentioned in the introduction, Theorem 2.2 has several obvious applications, and we focus on just one.
Suppose we want to compute a Boolean function f (x), x ∈ {0, 1}n , by the following parametrized linear
program. We have y = hy1 , . . . , ym i new variables and a set L(x, y) of linear inequalities or equalities over
R:
`1 (x, y) ≥ a1 , . . . , `r (x, y) ≥ ar , u1 (x, y) = b1 , . . . , ut (x, y) = bt .
We say that L(x, y) computes f , if for every x ∈ {0, 1}n ,
f (x) = 1 iff there exists y ∈ Rm such that L(x, y) is satisfied . (3.1)
In other words, f accepts precisely on the Boolean inputs
{x ∈ {0, 1}n : (∃y ∈ Rm ) (Ax + By ≥ a, Cx + Dy = b)} ,
where A, B,C, D, a, b are real matrices and vectors describing the linear system. We define the linear
separation complexity of f as the smallest r so that f can be computed as in (3.1) by a linear system
with r inequalities. Note that we disregard m, the number of extra variables, as well as t, the number of
equalities, in the definition. This is because both these parameters can be bounded in terms of n and r.
The geometric interpretation is as follows. A polyhedron P ⊆ Rn will be called a separating
polyhedron for f , if
f −1 (1) ⊆ P , f −1 (0) ∩ P = 0/ ,
T HEORY OF C OMPUTING, Volume 16 (9), 2020, pp. 1–12 4
O N THE C OMPLEXITY OF C OMPUTING A R ANDOM B OOLEAN F UNCTION OVER THE R EALS
i. e., the polyhedron contains all accepting inputs of f and excludes all its rejecting inputs. Following
[23, 18, 8], define the extension complexity of P as the smallest r such that P is a linear projection of a
polyhedron Q ⊆ Rm where Q can be defined using r inequalities (and any number of equalities). In this
language, the linear separation complexity of f equals the smallest r such that there exists a separating
polyhedron for f of extension complexity r.
While the phrase “linear separation complexity” is introduced here, the same concept has appeared
earlier. Already in [21], Valiant has observed that linear separation complexity is, up to a constant
factor, a lower bound on the Boolean circuit complexity of f . This appears again in the seminal paper of
Yannakakis [23]. A similar quantity was also investigated by Pudlák and Oliveira in [15] in the context of
proof complexity. Yannanakis’s paper started a fruitful direction of research into the extension complexity
of 0/1-polytopes. Rothvoß [18] has shown that there exists a polytope P ⊆ Rn with vertices in {0, 1}n
and extension complexity 2Ω(n) . Since then, the same was proved for explicit polytopes (see, e. g., [8, 19]
and references in the latter).
In our setting, the smallest separating polyhedron for f is simply the convex hull of accepting inputs
of f , P0 = conv( f −1 (1)). Hence, the result [18] says that there exists an f such that P0 has extponential
extension complexity. This, however, does not imply a lower bound on the linear separation complexity,
for there are infinitely many other separating polytopes. Furthermore, it is not apparent to the author how
to adapt Rothvoß’s proof to this setting. On the other hand, Theorem 2.2 readily implies the following
result.
Theorem 3.1. For every n, there exists a Boolean function f : {0, 1}n → {0, 1} with linear separation
complexity 2Ω(n) .
Proof. Assume that f can be computed by a linear system L(x, y) as in (3.1). It is easy to see that the
number of extra variables y can be bounded by r and the number of equalities by n. Hence, f can be
defined by a Σ1 -formula of size O((r + n)2 ). By Theorem 2.2, this means that r ≥ 2Ω(n) for some f .
Theorem 3.1 also implies the result in [18]. However, Rothvoß’s proof achieves better constants
hidden in Ω(n) and is definitely more informative. The reasoning of Theorem 3.1 could also be applied
to “semidefinite separation complexity” as considered in [5].
4 Proof of Theorem 2.1
We now show that quantifier alternations allow to efficiently define every Boolean function f . The idea is
to encode the truth table of f as a natural number, a f , so that the values of f can be efficiently recovered
from a f . The main ingredient is to show that over the field, we can argue about integers of doubly
exponential size. This part is reminiscent of the construction in [10, 7].
Let F be a field of characteristic zero. We identify a natural number n with the finite sum 1 + · · · + 1
of length n. A formula will be called constant-free, if it contains only the constants 0, 1 and −1.
Lemma 4.1. Given integers n and 1 ≤ k ≤ n, there exists a constant-free Σ2k−1 -formula An,k (x) of size
n
O(k2n/k ) such that An,k (x) defines the set {0, 1, . . . , 22 − 1}.
T HEORY OF C OMPUTING, Volume 16 (9), 2020, pp. 1–12 5
PAVEL H RUBE Š
i
Proof. We will first construct the formula using auxiliary constants, τ0 , τ1 , . . . , where τi := 22 . These
will be eliminated later. Given N a power of 2 and ` ≥ 1, we start by giving a Σ2`−1 -formula BN,` (x) of
`
size O(`N) defining the set {0, 1, . . . , 2N − 1}. Note that for an integer m ≥ 0, the function
gm (x0 , . . . , xN−1 ) = x0 + mx1 + · · · + mN−1 xN−1
is a bijection between {0, 1, . . . , m − 1}N and {0, 1, . . . , mN − 1}. We can set
!
N−1
^
BN,1 (x) := ∃x0 , . . . , xN−1 x = g2 (x0 , . . . , xN−1 ) ∧ (xi = 0 ∨ xi = 1) .
i=0
`
Given BN,` defining {0, 1, . . . , 2N − 1}, the formula
BN,`+1 (x) := ∃x0 , . . . , xN−1 x = g2N ` (x0 , . . . , xN−1 ) ∧ ∀z((z = x0 ∨ · · · ∨ z = xN−1 ) → Bn,` (z))
`+1
defines the set {0, 1, . . . , 2N − 1}. Moreover, we can write x = gm (x0 , . . . , xN−1 ) as
x = x0 + m(x1 + m(x2 + . . . ) . . . ) ,
which allows us to express x = g2N ` (x0 , . . . , xN−1 ) as a formula of size O(N) using only the constant
`
2N = τ` log2 N . Applying this recursively gives the required BN,` formula: its size is O(`N) and, converted
to prenex form, it is a Σ2`−1 -formula.
If k divides n, we can take B2n/k ,k as the formula An,k . In general, let
n
An,k (x) := ∃u x + u + 1 = 22 ∧ B2dn/ke ,k (u) ∧ B2dn/ke ,k (x) .
It remains to eliminate the constants τi . To this end, view them as free variables and let Tn0 be the
conjunction of the equations
τ0 = 2, τ1 = τ02 , . . . , τn0 = τn20 −1 .
0 n0
These equations have 22 , . . . , 22 as their only solution. Furthermore, An,k has used the constants τi with
i = n or i ≤ dn/ke(k − 1) ≤ 2n. Hence,
∃τ0 , . . . , τ2n (T2n ∧ An,k (x))
n
is a constant-free Σ2k−1 -formula defining {0, 1, . . . , 22 − 1}. The size of the formula is O(n + k2n/k )
which can be written as O(k2n/k ).
The following is a stronger version of Theorem 2.1.
Theorem 4.2. Let F be a field of characteristic zero. For every n and 1 ≤ k ≤ n, there exists a constant-
free Σ2k−1 -formula B(x1 , . . . , xn , y) of size O(k2n/k ) such that the following holds. For every f : {0, 1}n →
{0, 1} there exists a f ∈ F such that B(x1 , . . . , xn , a f ) defines the function f .
T HEORY OF C OMPUTING, Volume 16 (9), 2020, pp. 1–12 6
O N THE C OMPLEXITY OF C OMPUTING A R ANDOM B OOLEAN F UNCTION OVER THE R EALS
Proof. For x = hx1 , . . . , xn i ∈ {0, 1}n , let b(x) := ∑ni=1 2i−1 xi . Given f : {0, 1}n → {0, 1}, let
a f := ∑ f (x)2b(x) .
x∈{0,1}n
In other words, a f is the integer such that for every x, the b(x)-th bit of a f is f (x). Note that a f lies in
n
{0, 1, . . . , 22 − 1}. Furthermore, f (x) = 1 if and only if
n
∃y1 , y2 ∈ {0, 1, . . . , 22 − 1} , y1 < 2b(x) , a f = 2b(x)+1 y2 + 2b(x) + y1 . (4.1)
n
Using the previous lemma, the conditions y1 , y2 ∈ {0, 1, . . . , 22 − 1} can be replaced by An,k (y1 ), An,k (y2 ).
n
Also, the ordering y1 < z on {0, 1, . . . , 22 − 1} can be defined as ∃u(z = y1 + u + 1 ∧ An,k (u)). Finally,
n n
n i−1 x i−1 x i−1
2b(x) = 2∑i=1 2 i
= ∏ 22 i
= ∏(xi (22 − 1) + 1) .
i=1 i=1
i
This allows us to write 2b(x) and 2b(x)+1 = 2 · 2b(x) as O(n)-size terms using the auxiliary constants τi = 22 ,
i ≤ n − 1. As noted in the proof of the previous lemma, the constants can be defined by the formula
Tn−1 . Altogether, condition (4.1) can be written as a Σ2k−1 -formula of size O(n + k2n/k ), which in turn
simplifies to O(k2n/k ).
Let us remark that in the definition of a constant-free formula, one can insist that the formula contain
no constants at all: this is because 0, 1 and −1 can be defined by such a formula. Furthermore, in the
proof of Theorem 4.2, we did not use the fact that F is a field. It would be quite enough to assume that F is
a ring or even a semiring with multiplicative unit 1 such that the “natural numbers” 1, 1 + 1, 1 + 1 + 1, . . .
are distinct.
5 Proof of Theorem 2.2
Our proof of Theorem 2.2 uses tools from algebraic geometry and real algebraic geometry, namely,
counting the sign-patterns or zero-patterns of a polynomial map and quantifier elimination. The author
would be happy to see a more direct and self-contained proof at least for the case of Σ1 -formulas.
We first give an overview of the results required.
Sign-patterns of a polynomial map
For b ∈ R, let
1 , b > 0,
sgn(b) = 0 , b = 0,
−1 , b < 0.
Let f = h f1 (x1 , . . . , xn ), . . . , fm (x1 , . . . , xn )i be a sequence of real polynomials of degree at most d. For
a ∈ Rn , let sgn f (a) := hsgn f1 (a), . . . , sgn fm (a)i ∈ {−1, 0, 1}m , be the sign-pattern of f at a. Warren [22]
has obtained a bound on the number of sign-patterns of f lying in {−1, 1}m ; as noted by Alon [1], a
T HEORY OF C OMPUTING, Volume 16 (9), 2020, pp. 1–12 7
PAVEL H RUBE Š
similar bound applies to the total number of sign-patterns. Assuming 2m ≥ n and d ≥ 1, the number of
sign-patterns can be bounded as
|{sgn f (a) : a ∈ Rn }| ≤ (8edm/n)n . (5.1)
The same estimate clearly holds over any real closed field2 .
A similar bound holds for the number of zero-patterns over every field F.
For b ∈ F, let (
∗ 1 , b 6= 0,
sgn (b) :=
0 , b = 0.
For a ∈ Fn , let sgn∗ f (a) := hsgn∗ f1 (a), . . . , sgn∗ fm (a)i ∈ {0, 1}m , be the zero-pattern of f at a. A bound
on the number of zero-patterns of f has been obtained by Heintz [10]. An elementary linear algebra
proof of improved estimates was found more recently by Rónyai et al. in [17]. By [17], the number of
zero-patterns can be bounded (assuming d ≥ 1, m ≥ n) by
|{sgn∗ f (a) : a ∈ Fn }| ≤ (edm/n)n .
Quantifier elimination
The celebrated Tarski-Seidenberg theorem asserts that every formula over a real closed field is equivalent
to a quantifier-free formula. We are interested in the size of the resulting formula. It is known ([10, 7])
that in general, the size can increase double-exponentially if we allow a linear number of quantifier
alternations. The situation is better if the number of quantifier alternations is small. The result of Grigoriev
[9] (see also [3], Chapter 14, Theorem 14.16) implies the following: every Σk -formula A of size s is
O(k)
equivalent to a quantifier-free formula of size 2s . More specifically, A can be written as
G(sgn( f1 ) = σ1 , . . . , sgn( fm ) = σm ) , (5.2)
where f1 , . . . , fm are polynomials in the free variables of A, σ1 , . . . , σm ∈ {−1, 0, 1} and G : {0, 1}m →
{0, 1} is a Boolean function. Moreover, the degrees of the fi , the formula size of G, and the parameter m,
O(k)
can all be bounded by 2s .
A similar result holds over any algebraically closed field, as shown by Chistov and Grigoriev [6] (see
also Corollary 6.4 in [12]). Every Σk -formula A of size s is equivalent to a quantifier-free formula of the
form
G( f1 = 0, . . . , fm = 0) ,
O(k)
where m, the degrees of the fi , and the formula size of G, can again be bounded by 2s .
Let us remark that the cited papers contain more detailed information than presented here: they bound
the number of the fi in (5.2) and their degrees separately, in terms of the number of atomic formulas in A,
their degrees, and the number of quantifier alternations. Moreover, the constants in the big-O are different
in the two cases (algebraically closed versus real closed field).
2 Hence, also any ordered field
T HEORY OF C OMPUTING, Volume 16 (9), 2020, pp. 1–12 8
O N THE C OMPLEXITY OF C OMPUTING A R ANDOM B OOLEAN F UNCTION OVER THE R EALS
We now proceed to the proof of Theorem 2.2. At a high level, we use quantifier elimination to reduce
to the quantifier-free case, and apply Warren’s theorem to atoms of the quantifier-free formula.
For a formula A with no free variables, let [A] ∈ {0, 1} denote its truth-value. Let
β = hβ1 (y1 , . . . , yn ), . . . , βm (y1 , . . . , yn )i (5.3)
be a sequence of formulas with all their free variables among y1 , . . . , yn . For a ∈ Fn ,
[β (a)] := h[β1 (a)], . . . , [βm (a)]i ∈ {0, 1}m
will be called the truth-pattern of β at a. We want to bound the number of truth-patterns of β in terms of
its complexity,
Lemma 5.1. Let F be an algebraically closed field or a real closed field. Let β as in (5.3) be a
sequence of Σk -formulas, each of size at most s. Then the number of truth-patterns can be bounded as
O(k)
|{[β (a)] : a ∈ Fn }| ≤ (2s m)n .
Proof. First let us consider the real closed case. The bounds on quantifier elimination in (5.2) imply the
following. Given βi , there exists a sequence fi = h fi,1 , . . . , fi,mi i of polynomials in the variables y1 , . . . , yn
such that the truth value of βi (a), a ∈ Fn , is determined by the sign-pattern of fi at a. Moreover, mi as well
O(k)
as the degrees of fi, j are bounded by 2s . Let f be a sequence of all the polynomials fi, j , i ∈ {1, . . . , m},
O(k) O(k)
j ∈ {1, . . . , mi }. The length of the sequence is M ≤ m2s and each polynomial has degree d ≤ 2s .
Given a ∈ Fn , the truth-pattern of β at a is determined be the sign-pattern of f at a, and hence the number
of truth-patterns is at most the number of sign-patterns of f . Using (5.1), the latter can be bounded by
O(k)
(8edM)n which can be written3 as (2s m)n .
This completes the proof for the real closed case. In the case of algebraically closed fields the
argument is the same, replacing sign-patterns by zero-patterns and using the algebraically closed version
of quantifier elimination.
Proof of Theorem 2.2. Assume that s ≥ n is such that every Boolean function in n variables can be defined
by a Σk -formula of size at most s. Let F be the set of such formulas with free variables among x1 , . . . , xn .
Introduce fresh variables y = hy1 , . . . , ys i and z = hz1 , . . . , zs i. A formula S(x, y), with x = hx1 , . . . , xn i,
will be called a skeleton if (a) it contains only variables from x, y, z and no constant symbols, and (b)
its free variables are from x or y. We think of y as representing constants from F and z as names of
bound variables. Let S be the set of Σk -skeletons of size at most s. Hence, for every A(x) ∈ F there exists
S(x, y) ∈ S and a ∈ Fs such that A(x) = S(x, a) (up to renaming of the bound variables z). Unlike F, S is a
finite set. A skeleton is a string of symbols from the alphabet x, y, z, ∀, ∃, ∧, . . . of size O(s). Therefore,
|S| ≤ 2O(s log s) .
We will say that a skeleton S(x, y) defines a Boolean function f : {0, 1}n → {0, 1}, if there exists
a ∈ Fs such that S(x, a) defines f . Hence, every f is defined by some skeleton in S. We now want to
bound the number of functions defined by a given skeleton S(x, y) ∈ S. Let β be the sequence of the
3 As s ≥ 2, the additional constants can be swallowed by the big-O.
T HEORY OF C OMPUTING, Volume 16 (9), 2020, pp. 1–12 9
PAVEL H RUBE Š
2n formulas S(σ , y), σ ∈ {0, 1}n . Each formula in β has free variables in y. For a given a ∈ Fs , the
function defined by S(x, a) is uniquely determined by the truth-pattern of β at a: indeed, S(x, a) defines
the function f such that f (σ ) = [S(σ , a)] for all σ . Hence, the number of functions defined by S(x, y)
O(k)
is at most the number of truth-patterns of β . By the previous lemma, this can be bounded by (2s 2n )s
O(k)
which is of the form 2s (we assumed s ≥ n).
O(k)
Altogether, skeletons in S can define at most 2O(s log s) 2s Boolean functions. Since the total number
n
of functions is 22 , we must have s ≥ 2Ω(n/k) .
6 Open problems
The proof of Theorem 2.2 uses machinery from algebraic geometry and real algebraic geometry as a
black box. As a consequence, it teaches us little about the nature of the problem. For example, the
aforementioned result of Rothvoss [18] is formally a consequence of Theorem 2.2. But his proof provides
an additional insight into the geometry of polytopes which is completely lacking in our setting.
Problem 6.1. Find a more direct and self-contained proof of Theorem 2.2, at least for Σ1 -formulas.
This would be interesting especially over the reals. Already the case of linear separation complexity
from Section 3, where the Σ1 -formula contains only linear inequalities or equalities, seems to require a
new insight. On the other hand, the first ingredient of the current proof of Theorem 2.2 over algebraically
closed fields, counting zero-patterns of a polynomial map, has been given a simple proof in [17]. Hence,
the question may be easier in the algebraically closed setting.
Second, the upper and lower bounds given by Theorem 2.1 and 2.2 do not match exactly (they hardly
can, for the constants are hidden in Theorem 2.2). Theorem 2.1 implies that every Boolean function can
be defined by a Σ3 -formula of size O(2n/2 ). But for Σ1 - or Σ2 -formulas, we are left with the trivial upper
bound of 2n(1−o(1)) . Whether we can improve the constant in the exponent is intriguing already in the
case of Σ1 -formulas.
Problem 6.2. Over R, can every f : {0, 1}n → {0, 1} be defined by a Σ1 -formula of size O(2(1−ε)n ) for
some 0 < ε < 1?
Acknowledgement The author thanks Pavel Pudlák and James Lee for useful discussions, and the
editors László Babai and Benjamin Rossman for considerably improving to the paper.
References
[1] N OGA A LON: Tools from higher algebra. In Handbook of Combinatorics, volume 2, pp. 1749–1783.
MIT Press, 1996. Link at ACM DL. 2, 7
[2] L ÁSZLÓ BABAI , A NNA G ÁL , AND AVI W IGDERSON: Superpolynomial lower bounds for mono-
tone span programs. Combinatorica, 19(3):301–319, 1999. [doi:10.1007/s004930050058] 2
[3] S AUGATA BASU , R ICHARD P OLLACK , AND M ARIE -F RANÇOISE ROY: Algorithms in Real
Algebraic Geometry. Springer, 2006. [doi:10.1007/3-540-33099-2] 8
T HEORY OF C OMPUTING, Volume 16 (9), 2020, pp. 1–12 10
O N THE C OMPLEXITY OF C OMPUTING A R ANDOM B OOLEAN F UNCTION OVER THE R EALS
[4] L ENORE B LUM , F ILIPE C UCKER , M ICHAEL S HUB , AND S TEVE S MALE: Complexity and Real
Computation. Springer, 1998. [doi:10.1007/978-1-4612-0701-6] 2, 4
[5] J OP B RIËT, DANIEL DADUSH , AND S EBASTIAN P OKUTTA: On the existence of 0/1 polytopes
with high semidefinite extension complexity. Math. Program., 153(1):179–199, 2015. Preliminary
version in ESA’13. [doi:10.1007/s10107-014-0785-x, arXiv:1305.3268] 5
[6] A LEXANDER L. C HISTOV AND D IMA G RIGORIEV: Complexity of quantifier elimination in the
theory of algebraically closed fields. In Proc. 11th Internat. Symp. Math. Found. Comput. Sci.
(MFCS’84), pp. 17–31. Springer, 1984. [doi:10.1007/BFb0030287] 8
[7] JAMES H. DAVENPORT AND J OOS H EINTZ: Real quantifier elimination is doubly exponential. J.
Symbolic Comput., 5(1–2):29–35, 1988. [doi:10.1016/S0747-7171(88)80004-X] 5, 8
[8] S AMUEL F IORINI , S ERGE M ASSAR , S EBASTIAN P OKUTTA , H ANS R AJ T IWARY, AND RONALD
DE W OLF : Exponential lower bounds for polytopes in combinatorial optimization. J. ACM,
62(2/17):95–106, 2015. Preliminary version in STOC’12. [doi:10.1145/2716307] 5
[9] D IMA G RIGORIEV: Complexity of deciding Tarski algebra. J. Symbolic Comput., 5(1–2):65–108,
1988. [doi:10.1016/S0747-7171(88)80006-3] 8
[10] J OOS H EINTZ: Definability and fast quantifier elimination in algebraically closed fields. Theoret.
Comput. Sci., 24(3):239–277, 1983. [doi:10.1016/0304-3975(83)90002-6] 5, 8
[11] PAVEL H RUBEŠ AND A MIR Y EHUDAYOFF: Arithmetic complexity in ring extensions. Theory of
Computing, 7(8):119–129, 2011. [doi:10.4086/toc.2011.v007a008] 2
[12] D OUGLAS J OHN I ERARDI: The Complexity of Quantifier Elimination in the Theory of an Alge-
braically Closed Field. Ph. D. thesis, Cornell University, 1989. Conference version in STOC’89.
8
[13] M AURICIO K ARCHMER AND AVI W IGDERSON: On span programs. In Proc. of 8th IEEE
Structure in Complexity Theory Conf. (SCT’93), pp. 102–111. IEEE Comp. Soc. Press, 1993.
[doi:10.1109/SCT.1993.336536] 2
[14] PASCAL KOIRAN: Circuits versus trees in algebraic complexity. In Proc. 17th Symp. Theoretical
Aspects of Comp. Sci. (STACS’00), pp. 35–52. Springer, 2000. [doi:10.1007/3-540-46541-3_3] 2
[15] PAVEL P UDLÁK AND M ATEUS DE O LIVEIRA O LIVEIRA: Representations of monotone Boolean
functions by linear programs. ACM Trans. Comput. Theory, 11(4):22:1–22:31, 2019. Preliminary
version in CCC’17. [doi:10.1145/3337787, ECCC:TR17-106] 2, 5
[16] J ULIA ROBINSON: Definability and decision problems in arithmetic. J. Symbolic Logic, 14(2):98–
114, 1949. [doi:10.2307/2266510] 3
[17] L AJOS RÓNYAI , L ÁSZLÓ BABAI , AND M URALI K. G ANAPATHY: On the number of zero-patterns
of a sequence of polynomials. J. Amer. Math. Soc., 14(3):717–735, 2001. [doi:10.1090/S0894-0347-
01-00367-8] 2, 8, 10
T HEORY OF C OMPUTING, Volume 16 (9), 2020, pp. 1–12 11
PAVEL H RUBE Š
[18] T HOMAS ROTHVOSS: Some 0/1 polytopes need exponential size extended formulations. Math.
Program., 142(1):255–268, 2013. [doi:10.1007/s10107-012-0574-3, arXiv:1105.0036] 2, 5, 10
[19] T HOMAS ROTHVOSS: The matching polytope has exponential extension complexity. J. ACM,
64(6):41:1–41:19, 2017. Preliminary version in STOC’14. [doi:10.1145/3127497, arXiv:1311.2369]
5
[20] A MIR S HPILKA AND A MIR Y EHUDAYOFF: Arithmetic circuits: A survey of recent results and open
questions. Found. Trends Theor. Comput. Sci., 5(3–4):207–388, 2010. [doi:10.1561/0400000039] 2
[21] L ESLIE G. VALIANT: Reducibility by Algebraic Projections. In Logic and Algorithmic, volume 30
of Monographs of L’Enseignement Mathématique, pp. 365–380. 1982. 5
[22] H UGH E. WARREN: Lower bounds for approximations by nonlinear manifolds. Trans. Amer. Math.
Soc., 133(1):167–178, 1968. [doi:10.2307/1994937] 2, 7
[23] M IHALIS YANNAKAKIS: Expressing combinatorial optimization problems by linear programs. J.
Comput. System Sci., 43(3):441–466, 1991. Preliminary version in STOC’88. [doi:10.1016/0022-
0000(91)90024-Y] 2, 5
AUTHOR
Pavel Hrubeš
Researcher
Institute of Mathematics of ASCR
Prague, Czechia
hrubes math cas cz
http://www.math.cas.cz/homepage/main_page.php?id_membre=189
ABOUT THE AUTHOR
PAVEL H RUBEŠ graduated from Charles University in Prague in 2008 under the supervision
of Pavel Pudlák.
After a period of joyful postdocs in the U. S. and Canada, he became a mature worker
in the factory of academia. He contributes mainly to arithmetic circuit complexity and
proof complexity. His hobbies include mountaineering and brooding.
T HEORY OF C OMPUTING, Volume 16 (9), 2020, pp. 1–12 12