1
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ 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)? $\endgroup$
    – Joshua Grochow
    Commented May 23, 2016 at 23:25
  • $\begingroup$ @JoshuaGrochow I think both questions are interesting $\endgroup$
    – Alexey Milovanov
    Commented May 24, 2016 at 9:20

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.