Squaring Up by Selection: NP-Completeness at Three Simple Roots
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.
Related
- A Simple and General Approach to top-k Selection
- DS and AMDS Symbol-Pair Codes from Three Families of Simple Root Cyclic Codes
- Classification of Nijenhuis operators on three-dimensional multiplicative simple Bihom-Lie algebras
- Maximal subalgebras in the three exceptional simple finite-dimensional Lie superalgebras
- Weak Polynomial Completeness Does Not Imply Almost Polynomial Completeness
BibTeX
@misc{bassik2026squaring,
title = {{Squaring Up by Selection: NP-Completeness at Three Simple Roots}},
author = {Oren Bassik},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.28909},
eprint = {2609.28909},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.28909},
}
RIS
TY - UNPB
TI - Squaring Up by Selection: NP-Completeness at Three Simple Roots
AU - Oren Bassik
PY - 2026
DA - 2026/09/24
PB - arXiv
DO - 10.48550/arxiv.2609.28909
UR - https://arxiv.org/abs/2609.28909
AB - 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.
ER -