0
$\begingroup$

Is there an example of real polynomial representation of a Boolean function with $4$ variables whose polynomial degree is $2$ that depends on $4$ variables?

$\endgroup$
6
  • $\begingroup$ $a\text{ and }b \:\: \text{ xor } \:\: c\text{ and }d \;\;\;\;\;\;\;$ $\endgroup$ – user12859 Jan 13 '15 at 6:01
  • $\begingroup$ $a\hspace{-0.03 in}\cdot \hspace{-0.03 in}b \; + \; c\hspace{-0.03 in}\cdot \hspace{-0.03 in}d \;\;\;\;$ $\endgroup$ – user12859 Jan 13 '15 at 6:08
  • $\begingroup$ $a=b=c=d=1$ gives $2$ as value. This cannot be right as Boolean function have $0/1$ value. $\endgroup$ – Bread Winner Jan 13 '15 at 6:09
  • $\begingroup$ GF(2) $\;$ $\endgroup$ – user12859 Jan 13 '15 at 6:10
  • $\begingroup$ Corrected question to real polynomial. $\endgroup$ – Bread Winner Jan 13 '15 at 6:11
2
$\begingroup$

Yes. Using the convention that inputs and outputs are $\pm 1$, then the function is $$ \frac{a(x+y)+b(x-y)}{2}. $$ You could have found this function using exhaustive search – there are only $2^{16}$ functions on $4$ variables.

$\endgroup$
3
  • $\begingroup$ Is there a computer program which does this trick? $\endgroup$ – Bread Winner Jan 13 '15 at 22:45
  • 1
    $\begingroup$ Yes, a computer program which you write. I actually wrote it once, which is how I found this function in the first place. $\endgroup$ – Yuval Filmus Jan 13 '15 at 22:46
  • $\begingroup$ Interesting so some examples could be found by brute force. $\endgroup$ – Bread Winner Jan 13 '15 at 22:47

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.