| 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:
|
http://hdl.handle.net/10338.dmlcz/104096 |
| . |
| 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 inequalities.in '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 |
| . |
