cs.CC — Computational Complexity
Contributed by Frank Vega
For d≥3 with −d≡0,1(mod4), let h(−d) be the number of classes of primitive positive definite binary quadratic forms of discriminant −d. We prove that d↦h(−d) is computable in deterministic polynomial time with an oracle for a language in the second level Σ2P of the polynomial hierarchy. The proof uses only reduction theory of binary quadratic forms, Lagrange's theorem and Hermite normal forms; it does not assume the generalized Riemann hypothesis, does not take a generating set of the class group as input, and uses no randomness. A Σ2P oracle finds a generating set of O(logd) forms, and an NP oracle then determines the lattice of relations, whose index is h(−d). Consequently, if P=NP, class numbers of imaginary quadratic fields are computable in polynomial time. As an application, the number Dn of representations of n by the ternary form 8x2+2y2+16z2 in Tunnell's congruent number criterion equals 2h(−4n) for square-free n≡2(mod8) and vanishes for square-free n≡6(mod8); hence Dn lies in FPΣ2P on even square-free n, and an exact counting reduction from #SAT to Dn would collapse the polynomial hierarchy to Δ3P.
Primarily AI-generated textHuman understanding: all partsHermite normal formTunnell's theorembinary quadratic formsblack-box groupsclass numberscongruent numberscounting complexitypolynomial hierarchy