Computer Science group of Jagiellonian University for the project
"Constraint Satisfaction Problems: beyond the finite case" within the
Weave-Unisono program. For more information, visit
https://euraxess.ec.europa.eu/jobs/130184.
Short project description follows:
An instance of the Constraint Satisfaction Problem (CSP) consists of two
parts. The one part defines variables which may, for example, correspond to
tasks to be scheduled. The second part contains local restrictions on these
variables, saying, for instance, that certain tasks must take certain
amount of time or must be performed after other tasks are completed. The
question in the CSP is whether there exists a global assignment to the
variables, such that all the restrictions, usually called constraints, are
satisfied. In our running example a satisfying assignment defines an order
of performing the tasks. On the theoretical side, the formalism of CSPs
generalizes the Boolean satisfiability problem. When constraints are
modelled as relations over a finite domain, the CSP is always in NP.
However, depending on the allowed set of relations, the CSP might be
NP-complete (i.e., practically unsolvable by known algorithm) or in P
(i.e., "efficiently" solvable). This "dichotomy" is obtained using, so
called, algebraic approach to the CSP. The algebraic approach is a
direction of research based on a deep connection between two involved
mathematical theories: universal algebra and computational complexity.
Unfortunately, even the simplest scheduling problem requires considering
relations over an infinite domain. The aim of this project is to make a
next step beyond the finite-domain CSP and consider a larger class of
problems, including some infinite-domain CSPs. The problems that can be
modelled in such an extended framework involve scheduling, but also
problems in spatial and temporal reasoning and many other areas. The class
of problems is extended and thus the theories must follow suit: the new
research builds on computational complexity, universal algebra, and this
time model theory as well as Ramsey theory.
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
