Quantified Positive Temporal Constraints
Michal Wrona (University of Wroclav)

A quantified constraint satisfaction problem for a language L is a
version of a constraint satisfaction problem that allows universal
quantification in the instances. A language L is temporal positive iff it can positively defined over (Q, \leq). Recently it was shown that depending on L a quantified constraint satisfaction problem for a positive temporal language L is either in LOGSPACE, NLOGSPACE-complete, P-complete, NP-complete or PSPACE-complete. I will give an overview of results and techniques making up the classification with a special stress on complexity results.