Currently displaying 1 – 15 of 15

Showing per page

Order by Relevance | Title | Year of publication

A geometrical method in combinatorial complexity

Jaroslav Morávek — 1981

Aplikace matematiky

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.

On hardly linearly provable systems

Jaroslav Morávek — 1984

Aplikace matematiky

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.

Page 1

Download Results (CSV)