How can I transform the term $x>C$ (i.e. the term assumes the value $1$ if $x>C$ and assumes the value $0$ otherwise) to an arithmetic circuit that computes it?
Where $x$ is the input to the circuit and $C$ is a known constant.
$\begingroup$
$\endgroup$
10
-
3$\begingroup$ You can’t. Arithmetic circuits only compute polynomials, and the set of positive elements is not the zero set of a polynomial in any ordered ring. $\endgroup$– Emil JeřábekAug 31, 2014 at 19:46
-
1$\begingroup$ Well, if the ordered ring is an integral domain, then a nonconstant polynomial can only have finitely many zeros, whereas there are infinitely many positive elements. If it’s not a domain, the argument gets a bit more messy, but it still works out. $\endgroup$– Emil JeřábekAug 31, 2014 at 20:26
-
2$\begingroup$ What do you mean by $x>C$ then? A finite field can’t be ordered. Which ordered structure do you take $x$ and $C$ from, and how do you represent them by elements of the finite field? $\endgroup$– Emil JeřábekAug 31, 2014 at 20:45
-
5$\begingroup$ Bush: I suggest you try to reformulate the question to actually express what you are thinking of. $\endgroup$– Kristoffer Arnsfelt HansenSep 1, 2014 at 9:34
-
4$\begingroup$ You can use interpolation to write any function on a finite field as an arithmetic circuit. Do you have other requirements? $\endgroup$– Sasho NikolovSep 1, 2014 at 16:36
|
Show 5 more comments