caa a22 4500 463186915 CHVBK 20180406164856.0 cr unu---uuuuu 170326e20070901xx s 000 0 eng 10.1007/s10472-007-9085-y doi (NATIONALLICENCE)springer-10.1007/s10472-007-9085-y Subramani K. LDCSEE, West Virginia University, Morgantown, WV, USA aut On a decision procedure for quantified linear programs [Elektronische Daten] [K. Subramani] 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. Springer Science+Business Media B.V., 2007 Quantification nationallicence Linear programming nationallicence Alternating Turing machines nationallicence Polynomial-time decidability nationallicence coNP-hardness nationallicence Annals of Mathematics and Artificial Intelligence Springer Netherlands 51/1(2007-09-01), 55-77 1012-2443 51:1<55 2007 51 10472 https://doi.org/10.1007/s10472-007-9085-y text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10472-007-9085-y text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Subramani K. LDCSEE, West Virginia University, Morgantown, WV, USA aut NATIONALLICENCE 773 0- Annals of Mathematics and Artificial Intelligence Springer Netherlands 51/1(2007-09-01), 55-77 1012-2443 51:1<55 2007 51 10472 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer