# Counting points on curves

It is known (see "Counting curves and their projections" (free version) 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?

• 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)? May 23 '16 at 23:25
• @JoshuaGrochow I think both questions are interesting May 24 '16 at 9:20