<p>It is known (see "<a href="http://dx.doi.org/10.1007/BF01202042" rel="nofollow">Counting curves and their projections</a>" (<a href="https://cosec.bit.uni-bonn.de/fileadmin/user_upload/publications/pubs/gatkar93.pdf" rel="nofollow">free version</a>) by von zur Gathen, Karpinski, and Shparlinski) that the problem of finding the number of $\mathbb{F}_q$-rational points on a curve in sparse representation is $\mathsf{\# P}$ complete. Note that the degree of such curve can be exponentially large since sparse representation allows it. </p>

<p>But assume that the degree of a curve is not greater than some polynomial. Can we find the number of $\mathbb{F}_q$-rational points of this curve by using, say, constant iterations of Arthur-Merlin protocol?</p>

CC BY-SA 3.0
2016-05-23T23:25:51.420Z
Note that constantly many rounds of AM is the same complexity class as AM... In your question, do you mean that you have a *sparse* polynomial of bounded degree, or just a degree bound (*instead* of a sparsity bound)?
Joshua Grochow
CC BY-SA 3.0
2016-05-24T09:20:45.527Z
@JoshuaGrochow I think both questions are interesting
Alexey Milovanov
<cc.complexity-theory><nt.number-theory><algebra>
Counting points on curves
Alexey Milovanov
# Counting points on curves

(Asked by: username_0 on 2016-05-18)

It is known (see "[Counting curves and their projections](http://dx.doi.org/10.1007/BF01202042)" ([free version](https://cosec.bit.uni-bonn.de/fileadmin/user_upload/publications/pubs/gatkar93.pdf)) by von zur Gathen, Karpinski, and Shparlinski) that the problem of finding the number of $\mathbb{F}\_q$-rational points on a curve in sparse representation is $\mathsf{\# P}$ complete. Note that the degree of such curve can be exponentially large since sparse representation allows it.

But assume that the degree of a curve is not greater than some polynomial. Can we find the number of $\mathbb{F}\_q$-rational points of this curve by using, say, constant iterations of Arthur-Merlin protocol?

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

> **Comments:**
> **username_1**: Note that constantly many rounds of AM is the same complexity class as AM... In your question, do you mean that you have a *sparse* polynomial of bounded degree, or just a degree bound (*instead* of a sparsity bound)?  
> **username_0**: @JoshuaGrochow I think both questions are interesting  

---

## 0 answers

