Squaring Up by Selection: NP-Completeness at Three Simple Roots
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.28909
curl -X POST /api/v1/records/arxiv/2609.28909/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.28909/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'