This article concerns the computational complexity of a fundamental problem in number theory: counting points on curves and surfaces over finite fields. There is no subexponential-time algorithm known and it is unclear if it can be $\mathrm{NP}$-hard. Given a curve, we present the first efficient Arthur-Merlin protocol to certify its point-count, its Jacobian group structure, and its Hasse-Weil zeta function. We extend this result to a smooth projective surface to certify the factor $P_{1}(T)$, corresponding to the first Betti number, of the zeta function; by using the counting oracle. We give the first algorithm to compute $P_{1}(T)$ that is poly($\log q$)-time if the degree $D$ of the input surface is fixed; and in quantum poly($D\log q$)-time in general. Our technique in the curve case, is to sample hash functions using the Weil and Riemann-Roch bounds, to certify the group order of its Jacobian. For higher dimension varieties, we first reduce to the case of a surface, which is fibred as a Lefschetz pencil of hyperplane sections over $\mathbb{P}^{1}$. The formalism of vanishing cycles, and the inherent big monodromy, enable us to prove an effective version of Deligne's `theoreme du pgcd' using the hard-Lefschetz theorem and an equidistribution result due to Katz. These reduce our investigations to that of computing the zeta function of a curve, defined over a finite field extension $\mathbb{F}_{Q}/\mathbb{F}_{q}$ of poly-bounded degree. This explicitization of the theory yields the first nontrivial upper bounds on the computational complexity.

翻译：本文研究数论中一个基本问题的计算复杂度：有限域上曲线与曲面的点计数问题。目前尚无已知的亚指数时间算法，且其是否属于$\mathrm{NP}$-难问题尚不明确。对于给定曲线，我们提出了首个高效的Arthur-Merlin协议，用于验证其点计数、雅可比群结构及Hasse-Weil zeta函数。我们将此结果推广至光滑射影曲面，通过使用计数预言机，验证zeta函数中对应第一贝蒂数的因子$P_{1}(T)$。我们给出了首个计算$P_{1}(T)$的算法：当输入曲面的度$D$固定时，该算法具有poly($\log q$)时间复杂度；一般情况下具有量子poly($D\log q$)时间复杂度。在曲线情形中，我们的技术是利用Weil界和Riemann-Roch界采样哈希函数，以验证其雅可比群的阶数。对于高维代数簇，我们首先将问题约化至曲面情形，该曲面可纤维化为$\mathbb{P}^{1}$上超平面截面的Lefschetz铅笔。借助消失循环形式体系与固有的巨大单值性，我们利用硬Lefschetz定理和Katz的等分布结果，证明了Deligne‘theoreme du pgcd’的有效版本。这些方法将研究简化为计算定义在有限域扩张$\mathbb{F}_{Q}/\mathbb{F}_{q}$（具有多项式有界次数）上曲线的zeta函数。该理论的显式化首次为计算复杂度提供了非平凡的上界。