Vortrag im Schwerpunkt Reelle Geometrie und Algebra
Donnerstag, 14. Januar 2010, um 17:00 Uhr in F426 (Schwerpunktkolloquium) Manuel Bodirsky (Paris)
Constraint Satisfaction Problems over the Real Numbers
The feasibility problem for linear programs is a famous constraint satisfaction problem
that can be solved in polynomial time.
In this talk we study the question how far the constraint language of all linear
inequalities can be expanded by other semi-algebraic relations
such that the corresponding constraint satisfaction problem
can still be solved in polynomial time.
We also discuss how polymorphisms and the so-called universal algebraic approach can be
applied to study the complexity of real-valued constraint satisfaction problems.
