On hardly linearly provable systems. (English) Zbl 0551.68042

A well-known theorem of Rabin yields a ’dimensional’ lower bound on the width of complete polynomial proofs of a system of linear algebraic inequalities. In this note we investigate a practically motivated class of systems where the same lower bound can be obtained on the width of ’almost all’ ’non-complete’ linear proofs. The proof of our result is based on the Helly Theorem.


68Q25 Analysis of algorithms and problem complexity
15A39 Linear inequalities of matrices
90C05 Linear programming
Full Text: EuDML


[1] M. O. Rabin: Proving simultaneous positivity of linear forms. JCSS 6 : 639-650 (1972). · Zbl 0274.68022
[2] Joseph Stoer, Christoph Witzgall: Convexity and Optimization in Finite Dimensions I. Springer-Verlag, Berlin-Heidelberg-New York, J 970. · Zbl 0203.52203
[3] Ky Fan: On systems of linear inequalities. in ’Linear Inequalities and Related Systems’ (H. W. Kuhn and A. W. Tucker. Princeton Univ. Press, 1956. · Zbl 0072.37602
[4] David G. Luenberger: Introduction to Linear and Nonlinear Programming. Addison-Wesley Publishing Company, 1973. · Zbl 0297.90044
[5] J. W. Jaromczyk: An extension of Rabin’s complete proof concept. MFCS 1981, Lecture Notes in Computer Science 118, Springer-Verlag 1981, 321 - 326. · Zbl 0471.68026
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.