<html><head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body>
<p>-------- Forwarded Message --------</p>
<div class="moz-forward-container">
<table class="moz-email-headers-table" cellspacing="0" cellpadding="0" border="0">
<tbody>
<tr>
<th valign="BASELINE" nowrap="nowrap" align="RIGHT">Subject:
</th>
<td>[DMANET] Two post-doc positions in the Theoretical
Computer Science group of Jagiellonian University</td>
</tr>
<tr>
<th valign="BASELINE" nowrap="nowrap" align="RIGHT">Date: </th>
<td>Tue, 15 Aug 2023 21:54:08 +0200</td>
</tr>
<tr>
<th valign="BASELINE" nowrap="nowrap" align="RIGHT">From: </th>
<td>Marcin Kozik <a class="moz-txt-link-rfc2396E" href="mailto:marcin.a.kozik@gmail.com"><marcin.a.kozik@gmail.com></a></td>
</tr>
<tr>
<th valign="BASELINE" nowrap="nowrap" align="RIGHT">Reply-To:
</th>
<td><a class="moz-txt-link-abbreviated" href="mailto:marcin.kozik@uj.edu.pl">marcin.kozik@uj.edu.pl</a></td>
</tr>
<tr>
<th valign="BASELINE" nowrap="nowrap" align="RIGHT">To: </th>
<td><a class="moz-txt-link-abbreviated" href="mailto:dmanet@zpr.uni-koeln.de">dmanet@zpr.uni-koeln.de</a></td>
</tr>
</tbody>
</table>
<br>
<br>
Last reminder about two post-doctoral positions offered by the
Theoretical<br>
Computer Science group of Jagiellonian University for the project<br>
"Constraint Satisfaction Problems: beyond the finite case" within
the<br>
Weave-Unisono program. For more information, visit<br>
<a class="moz-txt-link-freetext" href="https://euraxess.ec.europa.eu/jobs/130184">https://euraxess.ec.europa.eu/jobs/130184</a>><br>
Short project description follows:<br>
<br>
An instance of the Constraint Satisfaction Problem (CSP) consists
of two<br>
parts. The one part defines variables which may, for example,
correspond to<br>
tasks to be scheduled. The second part contains local restrictions
on these<br>
variables, saying, for instance, that certain tasks must take
certain<br>
amount of time or must be performed after other tasks are
completed. The<br>
question in the CSP is whether there exists a global assignment to
the<br>
variables, such that all the restrictions, usually called
constraints, are<br>
satisfied. In our running example a satisfying assignment defines
an order<br>
of performing the tasks. On the theoretical side, the formalism of
CSPs<br>
generalizes the Boolean satisfiability problem. When constraints
are<br>
modelled as relations over a finite domain, the CSP is always in
NP.<br>
However, depending on the allowed set of relations, the CSP might
be<br>
NP-complete (i.e., practically unsolvable by known algorithm) or
in P<br>
(i.e., “efficiently” solvable). This “dichotomy” is obtained
using, so<br>
called, algebraic approach to the CSP. The algebraic approach is a<br>
direction of research based on a deep connection between two
involved<br>
mathematical theories: universal algebra and computational
complexity.<br>
Unfortunately, even the simplest scheduling problem requires
considering<br>
relations over an infinite domain. The aim of this project is to
make a<br>
next step beyond the finite-domain CSP and consider a larger class
of<br>
problems, including some infinite-domain CSPs. The problems that
can be<br>
modelled in such an extended framework involve scheduling, but
also<br>
problems in spatial and temporal reasoning and many other areas.
The class<br>
of problems is extended and thus the theories must follow suit:
the new<br>
research builds on computational complexity, universal algebra,
and this<br>
time model theory as well as Ramsey theory.<br>
<br>
</div>
</body>
</html>