The problem of calculation the number of rational points on curves over finite fields is $\#P$-complete - "Counting curves and their projections".
Is it true for calculation of number of rational points of Jacobians?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ I do not know what the #P complexity class is. In any case, the computations of the zeta functions of a curve and of its jacobian are essentially equivalent, and are equivalent to the computation of the number of points of $X$ in all finite extensions of the ground finite field of degree less than the genus of the curve. $\endgroup$– ACLCommented May 4, 2016 at 23:44
-
$\begingroup$ @ACL >the computations of the zeta functions of a curve and of its jacobian are essentially equivalent. I do not think that this is true in terms of computational complexity. For some curves we can compute number of $\mathbb{F}_3$-rational points of their Jacobians but we do not know such algorithms for computing characteristic polynomials of Frobenius - www-math.mit.edu/~poonen/papers/ants2.pdf $\endgroup$– Alexey MilovanovCommented May 5, 2016 at 0:06
Add a comment
|