{"id":"arxiv/2609.07769","url":"https://arxiv.org/abs/2609.07769","tags":["cs.IT","cs.CC","cs.CR","math.AC","math.AG"],"score":0,"title":"A Note on Binary Quadratic Systems and their relation to complexity theory","domain":"cs.IT","source":"arxiv","authors":["Gabriele Radici","Massimiliano Sala"],"reviews":0,"subject":"cs.IT","summary":"Deciding whether a system of multivariate quadratic equations over $\\mathbb F_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. $\\cup_{n\\geq 2} \\MQ_0(n)$ is a coNP-complete language, while $\\cup_{n\\geq 2} \\MQ_1(n)$ lies in DP. It is known that $\\lim_{n\\to \\infty}…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-07","reactions":{}}