Minimum-coordinate elimination on a simplex: polynomial first-step safety and coNP-complete correctness
Abstract
We study a deletion rule for strictly convex quadratic minimization on a simplex: compute the affine minimizer on the current face, permanently remove a most-negative coordinate, and repeat. Correctness is required for every linear term and every resolution of ties. We characterize first-step safety by a finite maximum principle for the constrained inverse, and correctness from every initial face by principal-inverse row inequalities. Correctness from the full simplex is a different property. The two properties coincide with at most four coordinates, but an explicit rational five-coordinate example separates them. An exact reachability condition explains the separation: boundary equalities in the constrained inverse restrict the tasks that can be entered on a facet. Away from these equalities, full-start and hereditary correctness coincide. We also determine the recognition complexity. First-step safety is decidable in polynomial bit time, by combining classical strict n-step-vector recognition with diagonal regularization. In contrast, full-start and hereditary correctness are coNP-complete, even on a reduction family with strict column diagonal maxima on every face. The proofs include the non-strict boundary and all affine anchors; explicit rational certificates for the finite examples are given in the text.
Related
- Symmetric group actions on the coordinate ring of the lower unipotent group and the polynomial ring with quantum parameters
- Polynomial minimum degree stability for $3$-chromatic graphs
- CLT for the Weight of the Minimum Spanning Arborescence on the Complete Directed Graph
- Calogero-Moser Polynomial Approximations and Dwork Congruences for Complete Flags
- Complete solution to the weak persistent center and isochronous center problems of cubic polynomial systems
BibTeX
@misc{kosachev2026minimumcoordinate,
title = {{Minimum-coordinate elimination on a simplex: polynomial first-step safety and coNP-complete correctness}},
author = {Arseny Kosachev},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.33908},
eprint = {2610.33908},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.33908},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Minimum-coordinate elimination on a simplex: polynomial first-step safety and coNP-complete correctness
AU - Arseny Kosachev
PY - 2026
DA - 2026/10/24
PB - arXiv
DO - 10.48550/arxiv.2610.33908
UR - https://arxiv.org/abs/2610.33908
AB - We study a deletion rule for strictly convex quadratic minimization on a simplex: compute the affine minimizer on the current face, permanently remove a most-negative coordinate, and repeat. Correctness is required for every linear term and every resolution of ties. We characterize first-step safety by a finite maximum principle for the constrained inverse, and correctness from every initial face by principal-inverse row inequalities. Correctness from the full simplex is a different property. The two properties coincide with at most four coordinates, but an explicit rational five-coordinate example separates them. An exact reachability condition explains the separation: boundary equalities in the constrained inverse restrict the tasks that can be entered on a facet. Away from these equalities, full-start and hereditary correctness coincide. We also determine the recognition complexity. First-step safety is decidable in polynomial bit time, by combining classical strict n-step-vector recognition with diagonal regularization. In contrast, full-start and hereditary correctness are coNP-complete, even on a reduction family with strict column diagonal maxima on every face. The proofs include the non-strict boundary and all affine anchors; explicit rational certificates for the finite examples are given in the text.
ER -