Previous |  Up |  Next


Title: On hardly linearly provable systems (English)
Author: Morávek, Jaroslav
Language: English
Journal: Aplikace matematiky
ISSN: 0373-6725
Volume: 29
Issue: 4
Year: 1984
Pages: 286-293
Summary lang: English
Summary lang: Czech
Summary lang: Russian
Category: math
Summary: 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 (noncomplete) linear proofs. The proof of our result is based on the Helly Theorem. (English)
Keyword: lower bound
Keyword: linear proofs
Keyword: Helly Theorem
MSC: 15A39
MSC: 68Q25
MSC: 90C05
idZBL: Zbl 0551.68042
idMR: MR0754080
DOI: 10.21136/AM.1984.104096
Date available: 2008-05-20T18:25:20Z
Last updated: 2020-07-28
Stable URL:
Reference: [1] M. O. Rabin: Proving simultaneous positivity of linear forms.JCSS 6 : 639-650 (1972). Zbl 0274.68022, MR 0451858
Reference: [2] Joseph Stoer, Christoph Witzgall: Convexity and Optimization in Finite Dimensions I.Springer-Verlag, Berlin-Heidelberg-New York, J 970.
Reference: [3] Ky Fan: On systems of linear 'Linear Inequalities and Related Systems' (H. W. Kuhn and A. W. Tucker, eds.). Princeton Univ. Press, 1956. Zbl 0072.37602, MR 0087901
Reference: [4] David G. Luenberger: Introduction to Linear and Nonlinear Programming.Addison-Wesley Publishing Company, 1973.
Reference: [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, MR 0652765


Files Size Format View
AplMat_29-1984-4_6.pdf 825.0Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo