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 lower bound for the number of comparisons is obtained, required by a computational problem of classification of an arbitrarily chosen point of the Euclidean space with respect to a given finite family of polyhedral (non-convex, in general) sets, covering the space. This lower bound depends, roughly speaking, on the minimum number of convex parts, into which one can decompose these polyhedral sets. The lower bound is then applied to the knapsack problem.
The paper is a contribution to the general theory of problems of discrete programming. Particularly, the difficulties of such problems are investigated by theoretical means.
In this note a class of convex polyhedral sets of functions is studied. A set of the considered class is non-emplty if it satisfies certain conditions. Using Theorem 1 of this paper in the case of multi-index transportations problems we obtain necessary conditions for the existence of a feasible solution to this problem.
Page 1