Squaring Up by Selection: NP-Completeness at Three Simple Roots

Source abstract

To solve an overdetermined polynomial system numerically, one first makes it square, usually by replacing the given equations with as many random linear combinations as there are unknowns. This is a provably safe step, but it can substantially enlarge the supports. The alternative is to keep that many of the given equations themselves. Selection preserves sparsity but risks geometry: a genuine solution can cease to be an isolated point of the subsystem's zero set. We show that deciding whether a safe choice exists is NP-complete, already for an explicit family of systems of degree three with radical ideal and exactly three simple rational solutions. For strong selection with the nondegenerate rational solutions supplied explicitly, three is the exact threshold when degrees are polynomially bounded: one or two solutions reduce to matroid intersection, three already give NP-completeness. Even without a degree bound, an arbitrarily long list never takes the decision problem beyond NP. On the hard family, five natural notions of a faithful subsystem coincide, and every failing choice fails visibly: its zero set contains an affine subspace through one of the three solutions. A degree-four variant shows that cost information does not help: every candidate that could possibly succeed has mixed volume exactly three, and the problem is NP-complete still. The construction realizes Karp's three-dimensional matching problem as the selection of a square subsystem from the given equations.