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.

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.

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

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

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.