# On hardly linearly provable systems

Aplikace matematiky (1984)

- Volume: 29, Issue: 4, page 286-293
- ISSN: 0862-7940

## Access Full Article

top## Abstract

top## How to cite

topMorávek, Jaroslav. "On hardly linearly provable systems." Aplikace matematiky 29.4 (1984): 286-293. <http://eudml.org/doc/15358>.

@article{Morávek1984,

abstract = {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.},

author = {Morávek, Jaroslav},

journal = {Aplikace matematiky},

keywords = {lower bound; linear proofs; Helly Theorem; lower bound; linear proofs; Helly Theorem},

language = {eng},

number = {4},

pages = {286-293},

publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},

title = {On hardly linearly provable systems},

url = {http://eudml.org/doc/15358},

volume = {29},

year = {1984},

}

TY - JOUR

AU - Morávek, Jaroslav

TI - On hardly linearly provable systems

JO - Aplikace matematiky

PY - 1984

PB - Institute of Mathematics, Academy of Sciences of the Czech Republic

VL - 29

IS - 4

SP - 286

EP - 293

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

LA - eng

KW - lower bound; linear proofs; Helly Theorem; lower bound; linear proofs; Helly Theorem

UR - http://eudml.org/doc/15358

ER -

## References

top- M. O. Rabin, Proving simultaneous positivity of linear forms, JCSS 6 : 639-650 (1972). (1972) Zbl0274.68022MR0451858
- Joseph Stoer, Christoph Witzgall, Convexity and Optimization in Finite Dimensions I, Springer-Verlag, Berlin-Heidelberg-New York, J 970.
- Ky Fan, On systems of linear inequalities, in 'Linear Inequalities and Related Systems' (H. W. Kuhn and A. W. Tucker, eds.). Princeton Univ. Press, 1956. (1956) Zbl0072.37602MR0087901
- David G. Luenberger, Introduction to Linear and Nonlinear Programming, Addison-Wesley Publishing Company, 1973. (1973)
- J. W. Jaromczyk, An extension of Rabin's complete proof concept, MFCS 1981, Lecture Notes in Computer Science 118, Springer-Verlag 1981, 321 - 326. (1981) Zbl0471.68026MR0652765

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.