Consider the language $L=\{f, q\}$ - the number of solutions of equations $f(x,y)=0$ in $\mathbb{F}_q^2$ is equal to zero modulo $2$, where $q = 2^m$. Does $L$ belong to $P$? to $NP$? ($f$ is written as $\sum a_{ij} x^i y^j. $)

  • $\begingroup$ $\oplus P$. Can you explain your interest in the problem? $\endgroup$ – Joshua Grochow Sep 16 '16 at 23:16
  • $\begingroup$ @JoshuaGrochow I have proved that if $f$ is given in sparse representation than this problem is $\oplus$-complete - arxiv.org/abs/1608.07564 $\endgroup$ – Alexey Milovanov Sep 17 '16 at 7:22
  • $\begingroup$ @JoshuaGrochow However I do not think that this is true if $f$ is given in Sparse representation. I know there are polynomial algortihms for some curves but I do not know about general one $\endgroup$ – Alexey Milovanov Sep 17 '16 at 7:25
  • $\begingroup$ It's worth specifying in the question that you are interested in the case where $f$ is given by the dense representation, then. It is also worth including in the statement of the question that in the sparse representation it is $\oplus P$-complete, that you already know it's obviously in $\oplus P$ in the dense representation, and that you're looking for evidence that it's not $\oplus P$-complete in the dense representation. None of this was obvious from the question itself (and also, there could potentially be other evidence against $\oplus P$-completeness besides being in P or NP). $\endgroup$ – Joshua Grochow Sep 18 '16 at 3:57

This language belongs to P. See Corollary 7.4 at "Algorithmic theory of zeta functions over finite fields" by Daqing Wan. (There $n$ is the number of variables of a hypersurface, $d$ is the total degree of it, and $q$ is the cardinality of the corresponding finite field.)

| cite | improve this answer | |

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.