On hardly linearly provable systems

Jaroslav Morávek

Aplikace matematiky (1984)

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

Abstract

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

How to cite

top

Morá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
  1. M. O. Rabin, Proving simultaneous positivity of linear forms, JCSS 6 : 639-650 (1972). (1972) Zbl0274.68022MR0451858
  2. Joseph Stoer, Christoph Witzgall, Convexity and Optimization in Finite Dimensions I, Springer-Verlag, Berlin-Heidelberg-New York, J 970. Zbl0203.52203
  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. (1956) Zbl0072.37602MR0087901
  4. David G. Luenberger, Introduction to Linear and Nonlinear Programming, Addison-Wesley Publishing Company, 1973. (1973) Zbl0297.90044
  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. (1981) Zbl0471.68026MR0652765

NotesEmbed ?

top

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.