A Note on Binary Quadratic Systems and their relation to complexity theory

Gabriele Radici, Massimiliano Sala

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…