### K. Subramani

*West Virginia University*

**Time:** Monday, June 30, 14.30 - 15.30

**Place:** Room E4-104, Fredrik Bajersvej 7

### On the complexity of 2 person rational games

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. 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 is
Totally Unimodular (TUM). 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.