ECCC-Report TR19-036https://eccc.weizmann.ac.il/report/2019/036Comments and Revisions published for TR19-036en-usWed, 12 Aug 2020 11:53:14 +0300
Revision 1
| On the complexity of computing a random Boolean function over the reals |
Pavel Hrubes
https://eccc.weizmann.ac.il/report/2019/036#revision1We 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. Wed, 12 Aug 2020 11:53:14 +0300https://eccc.weizmann.ac.il/report/2019/036#revision1
Paper TR19-036
| On the complexity of computing a random Boolean function over the reals |
Pavel Hrubes
https://eccc.weizmann.ac.il/report/2019/036We 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. Tue, 05 Mar 2019 16:26:34 +0200https://eccc.weizmann.ac.il/report/2019/036