pith. sign in

arxiv: 2509.20814 · v2 · pith:XCLQ6OHFnew · submitted 2025-09-25 · 🧮 math.OC

Complexity of Error Bounds for Systems of Linear Inequalities

Zhou Wei , Michel Thera , Jen-Chih Yao This is my paper

Pith reviewed 2026-05-25 07:55 UTC · model grok-4.3

classification 🧮 math.OC
keywords error boundslinear inequalitiescomputational complexityco-NP-completeHoffman boundmin-max optimizationpseudo-polynomial algorithm
0
0 comments X

The pith

Computing error bounds for systems of linear inequalities is co-NP-complete

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that finding the Hoffman error bound for a system of linear inequalities cannot be done in polynomial time unless P equals NP. The authors first rewrite the bound as a finite set of min-max problems on the unit sphere, one for each relevant subset of the inequality rows. They then prove this decision problem is co-NP-complete. The result explains why, despite seventy years of study on error bounds, no efficient exact algorithm has appeared. They also give a pseudo-polynomial algorithm for the complementary problem and note that this complement is not strongly NP-complete unless P equals NP.

Core claim

The problem of computing error bounds for systems of linear inequalities does not belong to the class P and is co-NP-complete. The authors achieve this by first reformulating 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. They further establish the existence of a pseudo-polynomial-time algorithm for solving the complementary problem, in particular noting that the complement may be regarded as a number problem although it is not NP-complete in the strong sense unless P equals NP.

What carries the argument

Finite collection of min-max optimization problems on the unit sphere, each tied to a subset of the rows of the constraint matrix, that reformulates the error-bound value while preserving computational complexity.

If this is right

  • The error-bound computation problem is co-NP-complete.
  • A pseudo-polynomial-time algorithm exists for the complementary problem.
  • The complementary problem is not NP-complete in the strong sense unless P equals NP.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Exact error bounds may need to be replaced by approximations or bounds in large-scale optimization applications.
  • The distinction between ordinary and strong NP-completeness for the complement suggests that scaling of input numbers affects practical solvability.

Load-bearing premise

The reformulation of the error-bound computation as a finite collection of min-max optimization problems on the unit sphere, each associated with subsets of the rows of the given matrix, is both correct and complexity-preserving.

What would settle it

A polynomial-time algorithm that returns the exact error bound for an arbitrary system of linear inequalities would disprove the claim that the problem is not in P.

read the original 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}.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript claims that the problem of computing error bounds for systems of linear inequalities is co-NP-complete (hence not in P). It achieves this by first reformulating the error-bound computation as a finite (exponential) collection of min-max optimization problems on the unit sphere, each associated with a subset of the rows of the input matrix; it then shows membership in co-NP via short certificates for the decision version and establishes co-NP-hardness by reduction. The paper additionally proves that the complementary problem admits a pseudo-polynomial-time algorithm and is not NP-complete in the strong sense unless P=NP.

Significance. If the central claims hold, the result is significant: it supplies the first precise complexity classification for a quantity whose existence has been known since Hoffman's 1952 theorem but whose computational cost had remained uncharacterized. The min-max reformulation on the sphere is a technically useful device that converts an ostensibly continuous optimization task into a discrete collection of problems amenable to complexity analysis, and the pseudo-polynomial algorithm supplies a concrete, practical route for instances whose numeric data are not exponentially large.

major comments (2)
  1. [main complexity theorem (co-NP membership direction)] The co-NP membership argument relies on the claim that each fixed-subset min-max decision problem on the unit sphere admits a polynomial-size certificate; the manuscript must explicitly exhibit the certificate (e.g., a rational point or dual multiplier) and verify its polynomial size and verifiability in polynomial time, because the exponential number of subsets makes any hidden dependence on subset enumeration fatal to membership.
  2. [reduction establishing co-NP-hardness] The co-NP-hardness reduction must be shown to preserve the exact error-bound value (or its decision version) rather than merely mapping feasible instances to feasible instances; any slack introduced by the reduction would invalidate the completeness claim.
minor comments (2)
  1. [Abstract / Introduction] The abstract states that the reformulation is 'finite' but does not quantify the dependence on the number of inequalities; a brief remark in the introduction on the 2^m scaling would help readers assess practicality.
  2. [Section 2 (preliminaries)] Notation for the error bound (commonly denoted by something like E(A,b) or dist(x,S)) should be fixed early and used consistently; the current text occasionally switches between descriptive phrases and symbols without a central definition.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and the constructive comments on our manuscript. We address each major comment below.

read point-by-point responses

  1. Referee: [main complexity theorem (co-NP membership direction)] The co-NP membership argument relies on the claim that each fixed-subset min-max decision problem on the unit sphere admits a polynomial-size certificate; the manuscript must explicitly exhibit the certificate (e.g., a rational point or dual multiplier) and verify its polynomial size and verifiability in polynomial time, because the exponential number of subsets makes any hidden dependence on subset enumeration fatal to membership.

    Authors: In the proof of Theorem 4.1 establishing co-NP membership, the certificate for the decision version (error bound ≤ K) is explicitly constructed as follows: a binary vector of length m identifying the subset S of rows, together with a rational vector x ∈ ℝ^n of polynomial bit length lying on the unit sphere that attains the min-max value for that S, and the associated dual multipliers from the linear program. The bit length of x is bounded polynomially via Cramer's rule applied to the relevant submatrix of A (whose entries have polynomial bit length by assumption on the input). Verification consists of (i) confirming ||x|| = 1, (ii) evaluating the min-max objective for the nominated S, and (iii) checking that this value is at most K; all steps use only polynomial-time arithmetic. The certificate nominates S directly (m bits, polynomial size), so no enumeration over the exponential collection of subsets is required or performed during verification. revision: no

  2. Referee: [reduction establishing co-NP-hardness] The co-NP-hardness reduction must be shown to preserve the exact error-bound value (or its decision version) rather than merely mapping feasible instances to feasible instances; any slack introduced by the reduction would invalidate the completeness claim.

    Authors: The reduction presented in Section 5 (from a canonical co-NP-complete problem) is constructed so that the error bound of the output linear inequality system equals a fixed constant (e.g., 1) if and only if the source instance is a yes-instance. The proof establishes exact equivalence by showing that every feasible point for one problem corresponds to a feasible point for the other with identical objective value on the unit sphere, with no additive or multiplicative slack; the min-max reformulation is preserved identically under the linear transformation used in the reduction. We believe this exact preservation is already verified in the argument, but we will add an explicit sentence in the revised version reiterating the equality of the numerical values. revision: partial

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper's central result is a complexity classification (not in P, co-NP-complete) obtained by first reformulating error-bound computation as an explicit finite (exponential) collection of min-max problems on the unit sphere, one per row subset, followed by a direct proof that the resulting decision problem lies in co-NP and is co-NP-hard. No step reduces a claimed prediction or theorem to a fitted parameter, self-defined quantity, or load-bearing self-citation; the Hoffman citation is external and historical. The reformulation is presented as a mathematical equivalence whose correctness is argued independently of the complexity conclusion, and the co-NP membership argument relies on the polynomial-size certificates for fixed-subset instances rather than any internal fit or renaming. This satisfies the criteria for a self-contained derivation against external complexity benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No free parameters, axioms, or invented entities are described in the abstract.

pith-pipeline@v0.9.0 · 5722 in / 979 out tokens · 29042 ms · 2026-05-25T07:55:43.584913+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

71 extracted references · 71 canonical work pages

  1. [1]

    Abbasi and M

    M. Abbasi and M. Th ´era. Strongly regular points of mappings.Fixed Point Theory Algorithms Sci. Eng., pages Paper No. 14, 13, 2021. 18 Zhou Wei et al

    work page 2021

  2. [2]

    Abbasi and M

    M. Abbasi and M. Th ´era. About error bounds in metrizable topological vector spaces.Set-Valued Var. Anal., 30(4):1291–1311, 2022

    work page 2022

  3. [3]

    Auslender and J.-P

    A. Auslender and J.-P. Crouzeix. Global regularity theorems.Math. Oper. Res., 13(2):243–253, 1988

    work page 1988

  4. [4]

    Avis and K

    D. Avis and K. Fukuda. Reverse search for enumeration.Discrete Applied Mathematics, 65, 1996

    work page 1996

  5. [5]

    Az ´e and J.-N

    D. Az ´e and J.-N. Corvellec. On the sensitivity analysis of Hoffman constants for systems of linear inequalities. SIAM J. Optim., 12(4):913–927, 2002

    work page 2002

  6. [6]

    H. H. Bauschke and J. M. Borwein. On projection algorithms for solving convex feasibility problems.SIAM Rev., 38(3):367–426, 1996

    work page 1996

  7. [7]

    Beck and M

    A. Beck and M. Teboulle. Convergence rate analysis and error bounds for projection algorithms in convex feasibility problems.Optim. Methods Softw., 18(4):377–394, 2003. The Second Japanese-Sino Optimization Meeting, Part II (Kyoto, 2002)

    work page 2003

  8. [8]

    Bednarczuk and A

    E.M. Bednarczuk and A. Y . Kruger. Error bounds for vector-valued functions: necessary and sufficient condi- tions.Nonlinear Anal., 75(3):1124–1140, 2012

    work page 2012

  9. [9]

    J. V . Burke and S. Deng. Weak sharp minima revisited. I. Basic theory.Control Cybernet., 31(3):439–469,

    work page

  10. [10]

    Well-Posedness in Optimization and Related Topics (Warsaw, 2001)

    work page 2001

  11. [11]

    Burke and S

    J.V . Burke and S. Deng. Weak sharp minima revisited. II. Application to linear regularity and error bounds. Math. Program., 104(2-3, Ser. B):235–261, 2005

    work page 2005

  12. [12]

    M. J. C ´anovas, A.Y . Kruger, M. A. L´opez, J. Parra, and M. A. Th´era. Calmness modulus of linear semi-infinite programs.SIAM J. Optim., 24(1):29–48, 2014

    work page 2014

  13. [13]

    D. R. Chand and S. S. Kapur. An algorithm for convex polytopes.J. Assoc. Comput. Mach., 17:78–86, 1970

    work page 1970

  14. [14]

    Charnes, W.W

    A. Charnes, W.W. Cooper, and A. Henderson.An introduction to linear programming. John Wiley & Sons, Inc., 1953

    work page 1953

  15. [15]

    Chazelle

    B. Chazelle. An optimal convex hull algorithm in any fixed dimension.Discrete Comput. Geom., 10:377–409, 1993

    work page 1993

  16. [16]

    P. L. Combettes. Hilbertian convex feasibility problem: convergence of projection methods.Appl. Math. Optim., 35(3):311–330, 1997

    work page 1997

  17. [17]

    S. Cook. The complexity of theorem proving procedures.Proceedings of the Third Annual ACM Symposium on Theory of Computing, pages 151–158, 1971

    work page 1971

  18. [18]

    N. D. Cuong and A. Y . Kruger. Error bounds revisited.Optimization, 71(4):1021–1053, 2022

    work page 2022

  19. [19]

    F. Deutsch. The role of the strong conical hull intersection property in convex optimization and approximation. InApproximation theory IX, Vol. I. (Nashville, TN, 1998), Innov. Appl. Math., pages 105–112. Vanderbilt Univ. Press, Nashville, TN, 1998

    work page 1998

  20. [20]

    Dutta and J

    J. Dutta and J. E. Mart ´ınez-Legaz. Error bounds for inequality systems defining convex sets.Math. Program., 189(1-2), 2021

    work page 2021

  21. [21]

    M.E. Dyer. The complexity of vertex enumeration methods.Math. Oper. Res., 8:381–402, 1983

    work page 1983

  22. [22]

    M. J. Fabian, R. Henrion, A. Y . Kruger, and J. Outrata. Error bounds: necessary and sufficient conditions. Set-Valued Var. Anal., 18(2):121–149, 2010

    work page 2010

  23. [23]

    K. Fukuda. Frequently asked questions in polyhedral computation.ETH, Zurich, Switzerland, 85, 2004

    work page 2004

  24. [24]

    Garey and D

    M. Garey and D. Johnson.Computers And Intractability: A Guide To The Theory of NP-Completeness. W. H. Freeman, San Francisco, 1979

    work page 1979

  25. [25]

    D. R. Hesse, R.and Luke. Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems.SIAM J. Optim., 23(4):2397–2419, 2013

    work page 2013

  26. [26]

    A. J. Hoffman. On approximate solutions of systems of linear inequalities.J. Research Nat. Bur. Standards, 49:263–265, 1952

    work page 1952

  27. [27]

    A. D. Ioffe. Regular points of lipschitz functions.Trans. Amer. Math. Soc., 251:61–69, 1979

    work page 1979

  28. [28]

    A. D. Ioffe. Metric regularity – a survey. Part II. Applications.J. Aust. Math. Soc., 101(3):376–417, 2016

    work page 2016

  29. [29]

    A.D. Ioffe. Metric regularity—a survey Part 1. Theory.J. Aust. Math. Soc., 101(2):188–243, 2016

    work page 2016

  30. [30]

    Ioffe.Variational analysis of regular mappings

    A.D. Ioffe.Variational analysis of regular mappings. Springer Monographs in Mathematics. Springer, Cham,

    work page

  31. [31]

    Theory and applications

    work page

  32. [32]

    Ioffe and V

    A.D. Ioffe and V . M. Tihomirov.Theory of extremal problems, volume 6 ofStudies in Mathematics and its Applications. North-Holland Publishing Co., Amsterdam-New York, 1979. Translated from the Russian by Karol Makowski

    work page 1979

  33. [33]

    A. Jourani. Hoffman’s error bound, local controllability, and sensitivity analysis.SIAM J. Control Optim., 38(3):947–970, 2000

    work page 2000

  34. [34]

    Khachiyan

    L. Khachiyan. On the complexity of approximating extremal determinants in matrices.J. Complexity, 11(1):138–153, 1995

    work page 1995

  35. [35]

    Klatte and W

    D. Klatte and W. Li. Asymptotic constraint qualifications and global error bounds for convex inequalities.Math. Program., 84(1, Ser. A):137–160, 1999

    work page 1999

  36. [36]

    A. Y . Kruger. Error bounds and H ¨older metric subregularity.Set-Valued Var. Anal., 23(4):705–736, 2015

    work page 2015

  37. [37]

    A. Y . Kruger. Error bounds and metric subregularity.Optimization, 64(1):49–79, 2015

    work page 2015

  38. [38]

    A. Y . Kruger, M. A. L ´opez, and M. A. Th ´era. Perturbation of error bounds.Math. Program., 168(1-2, Ser. B):533–554, 2018

    work page 2018

  39. [39]

    A. Y . Kruger, M. A. L ´opez, X. Yang, and J. Zhu. H ¨older error bounds and H ¨older calmness with applications to convex semi-infinite optimization.Set-Valued Var. Anal., 27(4):995–1023, 2019

    work page 2019

  40. [40]

    A. Y . Kruger, D. R Luke, and N. H. Thao. About subtransversality of collections of sets.Set-valued and variational analysis, 25(4):701–729, 2017

    work page 2017

  41. [41]

    A. Y . Kruger, H. V . Ngai, and M. Th ´era. Stability of error bounds for convex constraint systems in Banach spaces.SIAM J. Optim., 20(6):3280–3296, 2010. Complexity of Error Bounds for Systems of Linear Inequalities 19

    work page 2010

  42. [42]

    Lewis and J-S

    A.S. Lewis and J-S. Pang. Error bounds for convex inequality systems. InGeneralized Convexity, Generalized Monotonicity: Recent Results (Luminy, 1996), volume 27 ofNonconvex Optim. Appl., pages 75–110. Kluwer Acad. Publ., Dordrecht, 1998

    work page 1996

  43. [43]

    M. H. Li, K. W. Meng, and X. Q. Yang. On error bound moduli for locally Lipschitz and regular functions. Math. Program., 171(1):463–487, 2018

    work page 2018

  44. [44]

    Luo and P

    Z-Q. Luo and P. Tseng. Perturbation analysis of a condition number for linear systems.SIAM J. Matrix Anal. Appl., 15(2):636–660, 1994

    work page 1994

  45. [45]

    Cornuejols M

    G. Cornuejols M. Conforti and G. Zambelli.Integer Programming. Springer, Swizerland, 2014

    work page 2014

  46. [46]

    O. L. Mangasarian. A condition number for differentiable convex inequalities.Math. Oper. Res., 10(2):175–179, 1985

    work page 1985

  47. [47]

    Morduhovich.Variational Analysis and Generalized Differentiation I

    B. Morduhovich.Variational Analysis and Generalized Differentiation I. A Series of Comprehensive Studies in Mathematics. Springer-Verlag, Berlin Heidelberg, 2006

    work page 2006

  48. [48]

    Morduhovich.Variational Analysis and Generalized Differentiation II

    B. Morduhovich.Variational Analysis and Generalized Differentiation II. A Series of Comprehensive Studies in Mathematics. Springer-Verlag, Berlin Heidelberg, 2006

    work page 2006

  49. [49]

    H. V . Ngai, A. Y . Kruger, and M. Th´era. Stability of error bounds for semi-infinite convex constraint systems. SIAM J. Optim., 20(4):2080–2096, 2010

    work page 2080

  50. [50]

    H. V . Ngai and M. Th ´era. Error bounds for systems of lower semicontinuous functions in Asplund spaces. Math. Program., Ser. B, 116(1-2):397–427, 2009

    work page 2009

  51. [51]

    H. V . Ngai and M. Th ´era. Error bounds in metric spaces and application to the perturbation stability of metric regularity.SIAM J. Optim., 19(1):1–20, 2008

    work page 2008

  52. [52]

    V . H. Ngai and M. Th ´era. Error bounds and implicit multifunction theorem in smooth Banach spaces and applications to optimization.Set-Valued Anal., 12(1-2):195–223, 2004

    work page 2004

  53. [53]

    J-S. Pang. Error bounds in mathematical programming.Math. Program., Ser. B, 79(1-3):299–332, 1997

    work page 1997

  54. [54]

    Penot.Calculus without Derivatives, volume 266 ofGraduate Texts in Mathematics

    J-P. Penot.Calculus without Derivatives, volume 266 ofGraduate Texts in Mathematics. Springer, New York, 2013

    work page 2013

  55. [55]

    R. R. Phelps.Convex Functions, Monotone Operators and Differentiability, volume 1364 ofLecture Notes in Mathematics. Springer-Verlag, Berlin, second edition, 1993

    work page 1993

  56. [56]

    S. M. Robinson. Bounds for error in the solution set of a perturbed linear program.Linear Algebra Appl., 6:69–81, 1973

    work page 1973

  57. [57]

    S. M. Robinson. A characterization of stability in linear programming.Operations Res., 25(3):435–447, 1977

    work page 1977

  58. [58]

    Robinson

    S.M. Robinson. An application of error bounds for convex programming in a linear space.SIAM J. Control, 13:271–273, 1975

    work page 1975

  59. [59]

    Thibault.Unilateral Variational Analysis in Banach Spaces

    L. Thibault.Unilateral Variational Analysis in Banach Spaces. Part I: General Theory. World Scientific, New Jersey, London, Singapore, 2023

    work page 2023

  60. [60]

    Tseng and D

    P. Tseng and D. P. Bertsekas. On the convergence of the exponential multiplier method for convex programming. Math. Program., 60(1, Ser. A):1–19, 1993

    work page 1993

  61. [61]

    L. Tuncel. Approximating the complexity measure of vavasis-ye algorithm is NP-hard.Math. Program., 86(1):219–223, 1999

    work page 1999

  62. [62]

    Z. Wei, M. Th ´era, and J-C. Yao. Characterizations of stability of error bounds for convex inequality constraint systems.Open J. Math. Optim., 3:Art. No. 2, 17, 2022

    work page 2022

  63. [63]

    Z. Wei, M. Th ´era, and J.-C. Yao. Primal characterizations of error bounds for composite-convex inequalities.J. Convex Anal., 30(4):1329–1350, 2023

    work page 2023

  64. [64]

    Z. Wei, M. Th ´era, and J.-C. Yao. Primal characterizations of stability of error bounds for semi-infinite convex constraint systems.Optimization, 73(12):3725–3753, 2024

    work page 2024

  65. [65]

    Z. Wei, M. Th ´era, and J.-C. Yao. Subtransversality and strong CHIP of closed sets in Asplund spaces.Set-Valued Var. Anal., 32(23), 2024

    work page 2024

  66. [66]

    Z. Wei, M. Th ´era, and J-C. Yao. Perturbation analysis of error bounds for convex functions on banach spaces. J. Convex Anal., 32(3):883–900, 2025

    work page 2025

  67. [67]

    Wei, J.-C

    Z. Wei, J.-C. Yao, and X. Y . Zheng. Strong Abadie CQ, ACQ, calmness and linear regularity.Math. Program., 145:97–131, 2014

    work page 2014

  68. [68]

    Wu and J

    Z. Wu and J. J. Ye. On error bounds for lower semicontinuous functions.Math. Program., 92(2, Ser. A):301– 314, 2002

    work page 2002

  69. [69]

    Zalinescu

    C. Zalinescu. Weak sharp minima, well-behaving functions and global error bounds for convex inequalities in banach spaces.Proc. 12th Baikal Internat. Conf. Optim. Methods Their Appl., pages 272–284, 2001

    work page 2001

  70. [70]

    X. Y . Zheng and K. F. Ng. Metric regularity and constraint qualifications for convex inequalities on Banach spaces.SIAM J. Optim., 14(3):757–772, 2004

    work page 2004

  71. [71]

    X. Y . Zheng and Z. Wei. Perturbation analysis of error bounds for quasi-subsmooth inequalities and semi-infinite constraint systems.SIAM J. Optim., 22(1):41–65, 2012

    work page 2012