Abstract:Error bounds have been studied for more than seventy years, beginning with the seminal result of Hoffman (1952) [{\it J. Res. Natl. Bur. Standards}, 49 (1952), 263--265], which establishes an upper bound for the distance from an arbitrary point to the solution set of a linear system. Despite this long history, relatively little is known about the intrinsic computational complexity of error bounds.
In this paper, we investigate the complexity of error bounds for systems of linear inequalities. We first reformulate the problem as a finite collection of min--max optimization problems defined on the unit sphere and associated with subsets of the rows of the given matrix. We then prove that the problem does not belong to the class {\bf P}, while it is {\bf co\mbox{-}NP}-complete.
Furthermore, we establish the existence of a pseudo-polynomial-time algorithm for solving the complementary problem. In particular, the complement may be regarded as a number problem, although it is not {\bf NP}-complete in the strong sense unless {\bf P} = {\bf NP}.
| Subjects: | Optimization and Control (math.OC) |
| Cite as: | arXiv:2509.20814 [math.OC] |
| (or arXiv:2509.20814v2 [math.OC] for this version) | |
| https://doi.org/10.48550/arXiv.2509.20814 arXiv-issued DOI via DataCite |
From: Zhou Wei [view email]
[v1]
Thu, 25 Sep 2025 06:55:29 UTC (63 KB)
[v2]
Fri, 22 May 2026 02:26:42 UTC (32 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。