0
$\begingroup$

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.

$\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$ Aug 31 '14 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$ Aug 31 '14 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$ Aug 31 '14 at 20:45
  • 5
    $\begingroup$ Bush: I suggest you try to reformulate the question to actually express what you are thinking of. $\endgroup$ Sep 1 '14 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$ Sep 1 '14 at 16:36

Your Answer

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

Browse other questions tagged or ask your own question.