3
$\begingroup$

I have a polynomial $f(x_1,\ldots,x_{50})$ of 50 variables over binary field $GF(2)$. I want to evaluate at all $2^{50}$ points and check how many of them are 0. Ofcourse we can evaluate at all points and check them. Can we do faster than this using some memory?

$\endgroup$
4
$\begingroup$

This problem is in general #P-complete, as you can for example encode a SAT instance as a polynomial over GF(2) and reduce #SAT to this problem. So all the standard hardness results apply to this.

If you're happy with finding the fraction of evaluation points over which the polynomial vanishes, up to an additive constant $\epsilon$, then you can trivially evaluate at enough random points and take the empirical estimate.

$\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.