Logic List Mailing Archive

CfA: two assistant prof at the Theoretical Computer Science group of Jagiellonian University, Kraków (Polen), Deadline: 18 August 2023

Last reminder about two post-doctoral positions offered by the Theoretical 
Computer Science group of Jagiellonian University for the project "Constrai
nt Satisfaction Problems: beyond the finite case" within the Weave-Unisono 
program. For more information, visit https://euraxess.ec.europa.eu/jobs/130

RECTOR of the Jagiellonian University announces a selection procedure for t
he position of an ASSISTANT PROFESSOR (2 posts) Group of employees: Researc
h staff Faculty of Mathematics and Computer Science Field of science: Natur
al sciences

Short project description follows:

An instance of the Constraint Satisfaction Problem (CSP) consists of two pa
rts. The one part defines variables which may, for example, correspond to t
asks to be scheduled. The second part contains local restrictions on these 
variables, saying, for instance, that certain tasks must take certain amoun
t of time or must be performed after other tasks are completed. The questio
n 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 performi
ng the tasks. On the theoretical side, the formalism of CSPs generalizes th
e Boolean satisfiability problem. When constraints are modelled as relation
s 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 u
nsolvable by known algorithm) or in P (i.e., efficiently solvable). T
his dichotomy is obtained using, so called, algebraic approach to the
 CSP. The algebraic approach is a direction of research based on a deep con
nection between two involved mathematical theories: universal algebra and c
omputational complexity. Unfortunately, even the simplest scheduling proble
m requires considering relations over an infinite domain. The aim of this p
roject is to make a next step beyond the finite-domain CSP and consider a l
arger 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 c
lass of problems is extended and thus the theories must follow suit: the ne
w research builds on computational complexity, universal algebra, and this 
time model theory as well as Ramsey theory.
[LOGIC] mailing list, provided by DLMPST
More information (including information about subscription management) can
be found here: http://dlmpst.org/pages/logic-list.php