Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR19-036 | 5th March 2019 14:48

#### On the complexity of computing a random Boolean function over the reals

TR19-036
Authors: Pavel Hrubes
Publication: 5th March 2019 16:26
Keywords:

Abstract:

We say that a first-order formula $A(x_1,\dots,x_n)$ over $\mathbb{R}$ defines a Boolean function $f:\{0,1\}^n\rightarrow\{0,1\}$, if for every $x_1,\dots,x_n\in\{0,1\}$, $A(x_1,\dots,x_n)$ is true iff $f(x_1,\dots,x_n)=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\geq 1$ quantifier alternations, there exists an $f$ which requires a formula of size $2^{\Omega(n/k)}$.

The latter result implies several previously known as well as some new lower bounds in computational complexity. We note that (i) holds over any field of characteristic zero, and (ii) holds for any real closed or algebraically closed field.

ISSN 1433-8092 | Imprint