A Note on Binary Quadratic Systems and their relation to complexity theory
Abstract
Deciding whether a system of multivariate quadratic equations over 𝔽2 has a solution is a classical NP-complete problem, and remains so for square systems, with as many equations as variables. The hardness of this problem is one of the cornerstones of nowadays post-quantum cryptography. Let MQ0(n) and MQ1(n) denote the sets of square quadratic systems in n variables having respectively no solutions and exactly one solution. ∪n≥ 2 MQ0(n) is a coNP-complete language, while ∪n≥ 2 MQ1(n) lies in DP. It is known that limn→ ∞ |MQ1(n)|/|MQ0(n)|=1. Here we prove the explicit finite-n bounds |MQ0(n)|<|MQ1(n)| ≤ (1+1/(2n−1))|MQ0(n)|, More generally, let Qd be the space of polynomial functions (FF2)n→𝔽2 of degree at most d, and let αk count square systems in (Qd)n having exactly k solutions. Then α0<α1 ≤ (1+1/(2n−1))α0 , 2≤ d≤ n . The proof combines matroid and coding-theoretic methods. We interpret (FF2)n as the ground set of the evaluation matroid of Qd, express α0 and α1 through characteristic polynomials, and use a Whitney-type sign-reversing involution to show that the only terms that can push α1−α0 below α1/2n come from the elements of a matroid port. These are identified with minimal-support words of the Reed--Muller code RM(n−d−1,n)=RM(d,n)⊥; the required estimate then follows from the MacWilliams identity, the minimum-distance bound 2d+1, and the even-weight structure of the code.
Related
- Some applications of binary numeration systems with nonzero redundancy to the theory of locally complex functions
- The Complexity of KKT Points of Quadratic Programs with Polynomially-Bounded Coefficients
- The Undecidability of FO3 and the Calculus of Relations with Just One Binary Relation
- Polynomially Solvable Cases of the Quadratic Binary Optimization Problem with a Fixed Cardinality Constraint
- A Parallel Heuristic for the Fixed Cardinality Binary Quadratic Program
BibTeX
@misc{radici2026note,
title = {{A Note on Binary Quadratic Systems and their relation to complexity theory}},
author = {Gabriele Radici and Massimiliano Sala},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.07769},
eprint = {2609.07769},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.07769},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Note on Binary Quadratic Systems and their relation to complexity theory
AU - Gabriele Radici
AU - Massimiliano Sala
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2609.07769
UR - https://arxiv.org/abs/2609.07769
AB - Deciding whether a system of multivariate quadratic equations over 𝔽_2 has a solution is a classical NP-complete problem, and remains so for square systems, with as many equations as variables. The hardness of this problem is one of the cornerstones of nowadays post-quantum cryptography. Let MQ_0(n) and MQ_1(n) denote the sets of square quadratic systems in n variables having respectively no solutions and exactly one solution. ∪_n≥ 2 MQ_0(n) is a coNP-complete language, while ∪_n≥ 2 MQ_1(n) lies in DP. It is known that lim_n→ ∞ |MQ_1(n)|/|MQ_0(n)|=1. Here we prove the explicit finite-n bounds |MQ_0(n)|<|MQ_1(n)| ≤ (1+1/(2^n−1))|MQ_0(n)|, More generally, let Q_d be the space of polynomial functions (FF_2)^n→𝔽_2 of degree at most d, and let α_k count square systems in (Q_d)^n having exactly k solutions. Then α_0<α_1 ≤ (1+1/(2^n−1))α_0 , 2≤ d≤ n . The proof combines matroid and coding-theoretic methods. We interpret (FF_2)^n as the ground set of the evaluation matroid of Q_d, express α_0 and α_1 through characteristic polynomials, and use a Whitney-type sign-reversing involution to show that the only terms that can push α_1−α_0 below α_1/2^n come from the elements of a matroid port. These are identified with minimal-support words of the Reed--Muller code RM(n−d−1,n)=RM(d,n)^⊥; the required estimate then follows from the MacWilliams identity, the minimum-distance bound 2^d+1, and the even-weight structure of the code.
ER -