Complexity of Error Bounds for Systems of Linear Inequalities

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}.