Campus Event Calendar
Event Entry
What and Who
A model-theoretic approach to the complexity of constraint satisfaction problems
Manuel Bodirsky
Humboldt-Universität zu Berlin
Logik-Seminar
AG 1, AG 2, AG 3, AG 4, AG 5
AG Audience
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 28 June 2005
16:00
-- Not specified --
45 - FR 6.2
016
Saarbrücken
Abstract
Many problems in theoretical computer science can be formulated as
a constraint satisfaction problem. In such a problem, the aim is
to assign values to a given set of variables such that a given set
of constraints is satisfied. Constraint satisfaction problems are
abundant in theoretical computer science, and have applications for
instance in database theory, temporal and spacial reasoning, program
language analysis, and computational linguistics.
Typically, a constraint satisfaction problem has the following
two properties: adding constraints preserves unsatisfiability,
and forming variable-disjoint unions of instances preserves
satisfiability. A computational problem has these two properties
if and only if it can be formulated as a homomorphism problem for
a (finite or infinite) structure T. T is called the *template* of
the constraint satisfaction problem. For finite templates T, the
computational complexity of the corresponding constraint satisfaction
problems is intensively studied, and it is conjectured that they are
all either tractable or NP-complete.
Most of the recent progress on this question is based on the so-
called *algebraic approach* to constraint satisfaction. We present
model-theoretic results that generalize the algebraic approach from
finite to infinite templates.
a constraint satisfaction problem. In such a problem, the aim is
to assign values to a given set of variables such that a given set
of constraints is satisfied. Constraint satisfaction problems are
abundant in theoretical computer science, and have applications for
instance in database theory, temporal and spacial reasoning, program
language analysis, and computational linguistics.
Typically, a constraint satisfaction problem has the following
two properties: adding constraints preserves unsatisfiability,
and forming variable-disjoint unions of instances preserves
satisfiability. A computational problem has these two properties
if and only if it can be formulated as a homomorphism problem for
a (finite or infinite) structure T. T is called the *template* of
the constraint satisfaction problem. For finite templates T, the
computational complexity of the corresponding constraint satisfaction
problems is intensively studied, and it is conjectured that they are
all either tractable or NP-complete.
Most of the recent progress on this question is based on the so-
called *algebraic approach* to constraint satisfaction. We present
model-theoretic results that generalize the algebraic approach from
finite to infinite templates.
Contact
--email hidden
passcode not visible
logged in users only
Bahareh Kadkhodazadeh, 06/21/2005 17:00 -- Created document.