Geodesic
On hardly linearly provable systems
Applications of Mathematics, Tome 29 (1984) no. 4, pp. 286-293
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.21136/AM.1984.104096
Classification : 15A39, 68Q25, 90C05
Keywords: lower bound; linear proofs; Helly Theorem 
@article{10_21136_AM_1984_104096,
     author = {Mor\'avek, Jaroslav},
     title = {On hardly linearly provable systems},
     journal = {Applications of Mathematics},
     pages = {286--293},
     year = {1984},
     volume = {29},
     number = {4},
     doi = {10.21136/AM.1984.104096},
     mrnumber = {0754080},
     zbl = {0551.68042},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/AM.1984.104096/}
}
TY  - JOUR
AU  - Morávek, Jaroslav
TI  - On hardly linearly provable systems
JO  - Applications of Mathematics
PY  - 1984
SP  - 286
EP  - 293
VL  - 29
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.21136/AM.1984.104096/
DO  - 10.21136/AM.1984.104096
LA  - en
ID  - 10_21136_AM_1984_104096
ER  - 
%0 Journal Article
%A Morávek, Jaroslav
%T On hardly linearly provable systems
%J Applications of Mathematics
%D 1984
%P 286-293
%V 29
%N 4
%U http://geodesic.mathdoc.fr/articles/10.21136/AM.1984.104096/
%R 10.21136/AM.1984.104096
%G en
%F 10_21136_AM_1984_104096
Morávek, Jaroslav. On hardly linearly provable systems. Applications of Mathematics, Tome 29 (1984) no. 4, pp. 286-293. doi: 10.21136/AM.1984.104096

[1] M. O. Rabin: Proving simultaneous positivity of linear forms. JCSS 6 : 639-650 (1972). | MR | Zbl

[2] Joseph Stoer, Christoph Witzgall: Convexity and Optimization in Finite Dimensions I. Springer-Verlag, Berlin-Heidelberg-New York, J 970.

[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. | MR | Zbl

[4] David G. Luenberger: Introduction to Linear and Nonlinear Programming. Addison-Wesley Publishing Company, 1973.

[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. | MR | Zbl

Cité par Sources :