7
$\begingroup$

Does there exist an equivalent arithmetic circuit for each computable function?

I've been trying to wrap my head around the statement above, but haven't found a counter example although I believe the statement to be false.

What has made me curious is that I've read some theorems stating that a protocol (cryptograhy protocol theory) can compute any computable function, but then requires that the function should be specified as an arithmetic circuit.

$\endgroup$
  • $\begingroup$ Arithmetic circuits can only compute multinomials $\endgroup$ – Ariel May 1 '17 at 11:05
  • $\begingroup$ @Ariel - Can you describe to a programmer studying a little cryptography as a hobby what a multinomial is? :-) $\endgroup$ – Shuzheng May 1 '17 at 11:42
  • $\begingroup$ Arithmetic circuits compute functions on finitely many inputs. They can compute all polynomials. $\endgroup$ – Yuval Filmus May 1 '17 at 14:01
11
$\begingroup$

Arithmetic circuits compute a polynomial in their input. An arithmetic circuit over some field $\mathbb{F}$ with $n$ variables and total degree $d$ can compute functions $f:\mathbb{F}^n\rightarrow\mathbb{F}$ of the form:

$$f(x_1,...,x_n)=\sum\limits_{i_1+...+i_n\le d}\alpha _{i_1,...,i_n}\cdot x_1^{i_1}x_2^{i_2}...x_n^{i_n}$$

where $\alpha _{i_1,...,i_n}\in\mathbb{F}$ are the coefficients of the multivariate polynomial.

There are many computable functions that cannot be expressed as a polynomial, e.g. take $f:\mathbb{Q}\rightarrow\mathbb{Q}$ which is $1$ at $x=0$ and zero everywhere else. Since $f$ is non constant with an infinite number of zeros, it cannot be written as a univariate polynomial.

$\endgroup$
  • $\begingroup$ What is total degree d ? $\endgroup$ – Shuzheng May 1 '17 at 15:44
  • $\begingroup$ The maximum sum of powers $i_1+...+i_n$ such that the monomial $x_1^{i_1}...x_n^{i_n}$ appears with nonzero coefficient in the function computed by the circuit. Note that this already assumes any arithmetic circuit computs some polynomial, but you can show this easily by induction. $\endgroup$ – Ariel May 1 '17 at 16:31
14
$\begingroup$

Any computable boolean function with a fixed-length input can be computed by an arithmetic circuit. Consider any boolean function $f:\{0,1\}^n \to \{0,1\}$. Then there exists a multivariate polynomial $p(x_1,\dots,x_n)$ such that $f(x_1,\dots,x_n) = p(x_1,\dots,x_n)$ for all $x_1,\dots,x_n$, where arithmetic is done modulo two (i.e., over the field $\mathbb{F}_2=\{0,1\}$). Now every multivariate polynomial can be computed by a an arithmetic circuit, so $f$ can be computed by an arithmetic circuit.

In some sense the restrictions to fixed-length inputs is unavoidable, as any circuit inherently has a fixed number of inputs and a fixed number of outputs. So once you decide to focus on boolean functions, then the statement you saw in the crypto literature is justified: any boolean function that can be computed by a circuit, can be computed by an arithmetic circuit. And, any computable boolean function can be computed by arithmetic circuits, where we understand "computed" to mean that there is a family of arithmetic circuits, one per input length (the non-uniform model; this is unavoidable if you want to compute using circuits, as any one circuit can only have a fixed input length).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.