PreprintarXiv licencearXiv
Cubic Optimization over Three Nonnegative Integers Is NP-hard
Abstract
We prove that deciding whether an integer cubic polynomial takes a value at most one over three nonnegative integers is NP-hard. Hardness holds even when every feasible objective value is a positive integer, so every constructed instance has a finite, attained minimum. This establishes a sharp dimension boundary for the tractability of cubic integer optimization in fixed dimension. Our reduction from positive 1-in-3 satisfiability encodes Boolean constraints as modular conditions and uses an algebraic norm to construct a cubic objective whose minimum is one exactly for satisfiable formulas. The resulting six-parameter threshold language is NP-complete and admits short exponent certificates.
Related
- Comment on "The polarization hierarchy for polynomial optimization over convex bodies, with applications to nonnegative matrix rank"
- Ten unknowns for Hilbert's tenth problem over the integers
- Wild frieze patterns over the integers
- Nonnegative curvature on vector bundles over CP3 and its blow-up
- The zeroth stable homotopy groups of motivic spheres over the integers
BibTeX
@misc{wei2026cubic,
title = {{Cubic Optimization over Three Nonnegative Integers Is NP-hard}},
author = {Linchuan Wei},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.07269},
eprint = {2611.07269},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.07269},
}
RIS
TY - UNPB
TI - Cubic Optimization over Three Nonnegative Integers Is NP-hard
AU - Linchuan Wei
PY - 2026
DA - 2026/11/05
PB - arXiv
DO - 10.48550/arxiv.2611.07269
UR - https://arxiv.org/abs/2611.07269
AB - We prove that deciding whether an integer cubic polynomial takes a value at most one over three nonnegative integers is NP-hard. Hardness holds even when every feasible objective value is a positive integer, so every constructed instance has a finite, attained minimum. This establishes a sharp dimension boundary for the tractability of cubic integer optimization in fixed dimension. Our reduction from positive 1-in-3 satisfiability encodes Boolean constraints as modular conditions and uses an algebraic norm to construct a cubic objective whose minimum is one exactly for satisfiable formulas. The resulting six-parameter threshold language is NP-complete and admits short exponent certificates.
ER -