On hardly linearly provable systems
Aplikace matematiky (1984)
- Volume: 29, Issue: 4, page 286-293
- ISSN: 0862-7940
Access Full Article
top
Abstract
topHow 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 ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.