<p>This language belongs to P. See Corollary 7.4 at 
<a href="http://www.math.leidenuniv.nl/~psh/ANTproc/17wan.pdf" rel="nofollow">"Algorithmic theory of zeta functions
over finite fields"</a>
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.)</p>

CC BY-SA 3.0
2016-09-20T22:57:59.860Z
2016-09-20T22:57:59.860Z
Alexey Milovanov
<p>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. $)</p>

CC BY-SA 3.0
2016-09-16T23:16:28.193Z
[$\oplus P$](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Symbols#parityp). Can you explain your interest in the problem?
Joshua Grochow
CC BY-SA 3.0
2016-09-17T07:22:36.317Z
@JoshuaGrochow I have proved that if $f$ is given in sparse representation than this problem is $\oplus$-complete - http://arxiv.org/abs/1608.07564
Alexey Milovanov
CC BY-SA 3.0
2016-09-17T07:25:16.030Z
@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
Alexey Milovanov
CC BY-SA 3.0
2016-09-18T03:57:00.660Z
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).
Joshua Grochow
<cc.complexity-theory><algebra>
the number of rational points of a curve modulo 2
Alexey Milovanov
# the number of rational points of a curve modulo 2

(Asked by: username_0 on 2016-09-16)

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

**Tags:** cc.complexity-theory, algebra

> **Comments:**
> **username_1**: [$\oplus P$](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Symbols#parityp). Can you explain your interest in the problem?  
> **username_0**: @JoshuaGrochow I have proved that if $f$ is given in sparse representation than this problem is $\oplus$-complete - http://arxiv.org/abs/1608.07564  
> **username_0**: @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  
> **username_1**: 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).  

---

## 1 answers

### Answer by username_0 on 2016-09-20. Score: 1

This language belongs to P. See Corollary 7.4 at
["Algorithmic theory of zeta functions
over finite fields"](http://www.math.leidenuniv.nl/~psh/ANTproc/17wan.pdf)
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.)


---

