Metraipolis › archive › dc_8c602efde016

Deterministic NC Quadratic Root Counting in Characteristic Two — arXiv:2609.12669

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.12669
License (as archived)
CC0-1.0
Archived
2026-10-16T03:59:22.359Z
SHA-256 of the archived text
b993ba56340956b6e6265d1eb0f7a7f7b450aa8f2a14910281117520e9bba735
Stable URL of this page
https://metraipolis.com/documento/dc_8c602efde016

How to cite

Deterministic NC Quadratic Root Counting in Characteristic Two — arXiv:2609.12669 — arXiv (en), https://arxiv.org/abs/2609.12669 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_8c602efde016 (Metraipolis archive dc_8c602efde016, sha256 b993ba56340956b6e6265d1eb0f7a7f7b450aa8f2a14910281117520e9bba735)
BibTeX
@misc{dc8c602efde016,
  title = {Deterministic NC Quadratic Root Counting in Characteristic Two — arXiv:2609.12669},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.12669},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_8c602efde016; sha256 b993ba56340956b6e6265d1eb0f7a7f7b450aa8f2a14910281117520e9bba735},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.12669. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Counting satisfying assignments of Boolean formulas is a basic problem in theoretical computer science, with $\#3\text{-}\SAT$ as the standard $\SharpP$-complete problem. More generally, counting the solutions of a system of polynomial equations over $\F_2$ is $\SharpP$-complete. Here we focus on the more structured problem of counting the solutions of a single polynomial equation. For polynomial equations over finite fields, Ehrenfeucht and Karpinski \cite{computationalcomplexityofxorandcountingproblems1990} showed a sharp difference between degrees two and three: quadratic root counting is solvable in polynomial time, while the degree-three problem is $\SharpP$-complete. Their quadratic algorithm is sequential. For fixed finite fields, Ishai et al.~\cite{ishai2012randomizing} later gave deterministic parallel algorithms in odd characteristic and randomized parallel algorithms in characteristic two. We give a deterministic $\NC$ algorithm for exactly counting the solutions of a quadratic polynomial equation over every fixed finite field of characteristic two. Our algorithm separates the radical and uses the absolute trace to realize the bit distinguishing the two nondegenerate finite-field types as the Arf invariant \cite{arf1941untersuchungen} of a quadratic form over $\F_2$. It then recovers that invariant from an integral matrix using Browder's determinant criterion \cite{browder2006complete}. This replaces the randomized canonical-form step in the algorithm of Ishai et al.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-14 in cs.CC).
Categorie arXiv: Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2609.12669 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T03:50:48.481Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-09-14?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).