Accession Number : ADA018431

Title :   Spira's Theorems on Complete Linear Proofs of Systems of Linear Inequalities.

Descriptive Note : Technical rept.,

Corporate Author : WASHINGTON UNIV SEATTLE DEPT OF MATHEMATICS

Personal Author(s) : Klee,Victor

Report Date : SEP 1975

Pagination or Media Count : 22

Abstract : Motivated by questions of computational complexity, M. Rabin introduced the notion of a complete proof of a system of inequalities. The theorems of Rabin and P. Spira concerning that notion can all be interpreted as statements about partial coverings of convex polyhedra. Both papers are interesting and treat questions of fundamental importance for the study of computational complexity, but only Rabin's paper is correct in all respects. The present note contains counterexamples to some of Spira's results and establishes a correct version of one of them.

Descriptors :   *Inequalities, Computations, Convex sets, Theorems, Linear systems

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE