On a decision procedure for quantified linear programs |
| |
Authors: | K Subramani |
| |
Affiliation: | (1) LDCSEE, West Virginia University, Morgantown, WV, USA |
| |
Abstract: | Quantified linear programming is the problem of checking whether a polyhedron specified by a linear system of inequalities
is non-empty, with respect to a specified quantifier string. Quantified linear programming subsumes traditional linear programming,
since in traditional linear programming, all the program variables are existentially quantified (implicitly), whereas, in
quantified linear programming, a program variable may be existentially quantified or universally quantified over a continuous
range. In this paper, the term linear programming is used to describe the problem of checking whether a system of linear inequalities
has a feasible solution. On account of the alternation of quantifiers in the specification of a quantified linear program
(QLP), this problem is non-trivial. QLPs represent a class of declarative constraint logic programs (CLPs) that are extremely
rich in their expressive power. The complexity of quantified linear programming for arbitrary constraint matrices is unknown.
In this paper, we show that polynomial time decision procedures exist for the case in which the constraint matrix satisfies
certain structural properties. We also provide a taxonomy of quantified linear programs, based on the structure of the quantifier
string and discuss the computational complexities of the constituent classes.
This research has been supported in part by the Air Force Office of Scientific Research under contract FA9550-06-1-0050. |
| |
Keywords: | Quantification Linear programming Alternating Turing machines Polynomial-time decidability coNP-hardness |
本文献已被 SpringerLink 等数据库收录! |
|