Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.20814 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916037456297984 |
|---|---|
| author | Wei, Zhou Thera, Michel Yao, Jen-Chih |
| author_facet | Wei, Zhou Thera, Michel Yao, Jen-Chih |
| contents | 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}. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_20814 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Complexity of Error Bounds for Systems of Linear Inequalities Wei, Zhou Thera, Michel Yao, Jen-Chih Optimization and Control 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}. |
| title | Complexity of Error Bounds for Systems of Linear Inequalities |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2509.20814 |