Extended Constraint Satisfaction Problems


Joanna Ochremiak


Warsaw, 24th February 2016

$3$-colorability




Question: Can we color this graph?

$3$-colorability




Question: Can we color this graph?

$3$-colorability




Question: Can we color this graph?

$3$-colorability




Question: Can we color this graph?

Constraint Satisfaction Problem


Question: Can we assign values to variables so that all the constraints are satisfied?

Complexity of CSP


A CSP template $\Gamma$ is a set of types of constraints.


Problem: CSP$(\Gamma)$

Input: CSP instance with constraints from $\Gamma$

Decide: Is there an assignment satisfying all the constraints?


CSP Dichotomy Conjecture. For every finite template $\Gamma$, the problem CSP$(\Gamma)$ is solvable in polynomial time or NP-complete.

Max-cut


cost = 5 cost = 2

Goal: Find a coloring with minimal cost.

Valued CSP

Valued CSP


Goal: Find an assignment with minimal cost.

$2$-colorability

Goal: Find a coloring with minimal cost.

Complexity of VCSP


Problem: VCSP$(\Gamma)$

Input: VCSP instance with (valued) constraints from $\Gamma$

Goal: Find an assignment with minimal cost.


VCSP Dichotomy Conjecture. For every finite set of types of (valued) constraints $\Gamma$, the problem VCSP$(\Gamma)$ is solvable in polynomial time or NP-hard.


Theorem (Kozik, O.). If Pol$^+(\Gamma)$ does not have a cyclic operation, then VCSP$(\Gamma)$ is NP-hard.

$3$-colorability


Question: Can we color this graph?

$3$-colorability


Question: Can we color this graph?

FO-definable Instance


$\{ ab \ | \ a,b \in \mathbb{A}, a \neq b \}$ - vertices


$\{ \{ab,bc\} \ | \ a,b,c \in \mathbb{A}, a \neq b \wedge b \neq c \wedge a \neq c \}$ - edges

Definable CSP

Definable CSP


Problem: def-CSP$(\Gamma)$

Input: FO-definable CSP instance over $\Gamma$

Decide: Is there an assignment satisfying all the constraints?


A template $\Gamma$ is locally finite if every constraint allows only finitely many values for each variable.


Theorem (Klin, Kopczyński, O., Toruńczyk). If $\Gamma$ is locally finite, then def-CSP$(\Gamma)$ is decidable.


TM with Atoms


I ab bc eb ae eb A I ab bc R ab bc eb ae eb B B ... ab bc bc ce ad B B ... language of paths States: I, ab, bc,... , A, R

Turing machine with atoms is a Turing machine whose alphabet, state space, and transition relation are FO-definable sets.

Standard Alphabets


An alphabet $\mathcal{A}$ is standard iff every language $\mathcal{L}$ over $\mathcal{A}$ recognisable by a nondeterministic TMA is recognisable by some deterministic TMA.


Theorem (Bojańczyk, Klin, Lasota, Toruńczyk). There exists a non-standard alphabet.


Theorem (Klin, Lasota, O., Toruńczyk). An alphabet $\mathcal{A}$ is standard iff a CSP template $\Gamma_{\mathcal{A}}$ has a majority polymorphism.

Polymorphisms


A function $f \colon D^k \rightarrow D$ is a polymorphism of a relation $R \subseteq D^n$ if

$$\begin{array}{llcccrc} \mathbf{x_1} = & ( & x_1^1, & \ldots & , x_1^n & ) & \in R \\ & & \vdots & & \vdots \\ \mathbf{x_k} = & ( & x_k^1, & \ldots & , x_k^n & ) & \in R \\[.2em] \hline \hline & ( & f(x_1^1, \ldots, x_k^1), & \ldots & , f(x_1^n, \ldots, x_k^n) & ) & \in R \end{array}$$
A CSP template $\Gamma$ is a set of relations over a set of values $D$.

A function $f \colon D^k \rightarrow D$ is a polymorphism of a template $\Gamma$ if it is a polymorphism of every relation in $\Gamma$.

Majority || Complexity || Weighted Polymorphisms

Majority



Polymorphisms || Complexity || Weighted Polymorphisms

Complexity of CSP



Theorem (Bulatov, Krokhin, Jeavons). If every polymorphism of $\Gamma$ is a polymorphism of $R$, then CSP$(\Gamma \cup \{R \})$ is polynomial-time reducible to CSP$(\Gamma)$.

Polymorphisms characterize the complexity of CSP.


Weighted Polymorphisms || Complexity of VCSP

Complexity of VCSP



Theorem (Cohen, Cooper, Creed, Jeavons, Živný). If every weighted polymorphism of $\Gamma$ is a weighted polymorphism of $R$, then VCSP$(\Gamma \cup \{R \})$ is polynomial-time reducible to VCSP$(\Gamma)$.

Weighted polymorphisms characterize the complexity of VCSP.


Weighted Polymorphisms

Weighted Polymorphisms


Let $R \ \colon \ D^n \rightarrow \mathbb{Q} \cup \{\infty\}$ be a weighted relation.


A weighted polymorphism of $R$ is a probability distribution $\omega$ on the set of $m$-ary functions such that for any $n$-tuples ${\bf x_1}, \dots, {\bf x_m}$, such that $R({\bf x_i}) < \infty$, $$\sum_{g \ \in \ supp(\omega)} \omega(g) R(g({\bf x_1},\dots,{\bf x_m})) \leq {1\over m} (R({\bf x_1})+\dots+R({\bf x_m})),$$ where $supp(\omega)$ is the set of operations to which $\omega$ assigns a positive probability.

Polymorphisms || Complexity of VCSP

Non-standard Alphabet


\[ \{(a,c,e),(a,d,f),(b,c,f),(b,d,e)\} \]