0
$\begingroup$

Let the polynomial be in $f$ be a map from $\Bbb{Z}_2^k \to \Bbb{Z}_2$, defined by

$f = 1 + \sum_{i=1}^k x_i + \sum_{i\neq j; i,j = 1}^k x_i x_j + \dots + x_1 x_2 \cdots x_k$

Then I want to show that $f$ can be evaluated in polynomial time in $k$.

For instance. $k= 1$:

$f = 1 + x_1$

For $k = 2$:

$f = 1 + x_1( 1 + x_2)$

$k = 3$:

$f = 1 + x_3 + x_2(x_3 + 1) + x_1(x_3 + x_2(x_3 + 1) + 1) = \\ 1 + E_1 + x_1 (E_1 + 1),$

where $E_1 = x_3 + x_2(x_3 + 1)$

See Wolfram Alpha for $k= 4$ case.

$f = 1 + E_2 + x_2(E_2 + 1), \ \ \ E_2 = \dots$

$\endgroup$
  • $\begingroup$ Ummm, that expression doesn't work. Do you mean $\sum$ everywhere you wrote $\prod$? For example, $k=2$ gives: $1+x_1x_2 + x_1^2x_2^2$. $\endgroup$ – Thomas Andrews Apr 19 '14 at 18:43
  • $\begingroup$ @ThomasAndrews that's right $\endgroup$ – Shine On You Crazy Diamond Apr 19 '14 at 18:50
  • $\begingroup$ Then your formula for $k=2$ is still incorrect. It should be $1+(x_1+x_2)+2x_1x_2$. I suspect you want $i<j$ in the sum $\sum_{i\neq j, i,j=1}^n$, but I'm just guessing. $\endgroup$ – Thomas Andrews Apr 19 '14 at 18:55
  • $\begingroup$ It looks to me like the question intends to be factored as $(1+x_1)(1+x_2)\dots(1+x_k)$, which has an easy $O(k)$ computation, but I'm just guessing. $\endgroup$ – Thomas Andrews Apr 19 '14 at 18:57
  • $\begingroup$ @ThomasAndrews thank you! That means it's not the right polynomial I'm after. $\endgroup$ – Shine On You Crazy Diamond Apr 19 '14 at 22:19

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.