156 problems

For a finite relational structure $\mathbb{A}$, let $CSP(\mathbb{A})$ denote the associated constraint satisfaction problem. Feder–Vardi dichotomy conjecture. The complexity of…

A label-cover instance consists of variables, an alphabet, and constraints between variable pairs; a constraint is bijective when each label on either variable determines exactly o…

Bodirsky–Pinsker conjecture. $\operatorname{CSP}(\mathbb C)$ is either in P or NP-complete.

OGP computational-hardness conjecture. OGP is a marker of computational hardness: instances with the OGP cannot be solved efficiently by the relevant algorithmic classes.

Brakensiek–Guruswami conjecture. For every $k\geq 1$ and $n\geq 3$, the problem

Let $\bA$ be an algebra with a Taylor term in its clone, and let $R$ be a finite set of relations compatible with $\bA$. Write $CSP(R)$ for the constraint satisfaction problem over…

Let $\mathbb{A}=\langle A;\mathscr{R}\rangle$ be a finite core relational structure of finite relational signature. A polymorphism of $\mathbb{A}$ is an operation that is a homomor…

Bodirsky–Pinsker tractability conjecture. If the model-complete core of $fmathbb A$ has no such expansion $fmathbb C$ for which $\operatorname{Pol}(fmathbb C)$ has a continuous clo…

Let $\Gamma$ be a finite relational structure, under the usual conditions that may be assumed without loss of generality. Write $\operatorname{CSP}(\Gamma)$ for its constraint sati…

A reduction from general finite constraint satisfaction problems to digraph constraint satisfaction problems maps a relational structure to a digraph while preserving the relevant…

A digraph CSP is a constraint satisfaction problem whose fixed template is a directed graph. Solvability by the few subpowers algorithm is the algorithmic property described in the…

Let $\mathbb{A}$ be a finite relational structure that is a core, meaning that it has no proper retract. Its algebra of polymorphisms consists of the operations on its domain prese…

Creignou–Daude conjecture. Hypothesis A holds for random constraint satisfaction problems with domain size two.

Fix an integer $d>1$. Let $\Phi=(X,Y,\Psi,W)$ be a weighted bipartite $d$-to-$1$ label-cover instance with label sets $\{1,\ldots,R\}$ and $\{1,\ldots,R/d\}$ and total edge weight…

Let $G={\rangle (V,E),2R,\Psi\langle}$ be a label-cover instance whose constraints are alpha-constraints, where an alpha-constraint is defined by permutations…

Dense-solution-region conjecture. Algorithmic success is associated with the existence of dense regions of solutions which, despite being rare and invisible to the equilibrium meas…

Let $\mathbf{a}$ be a finite idempotent algebra, and let $\Gamma(\mathbf{a})$ be its associated relational clone. The source has established that if $\mathbf{a}$ has no Taylor term…

Let $\mathbf{a}$ be a finite idempotent algebra, and let $\Gamma(\mathbf{a})$ denote the constraint language consisting of the relations compatible with all operations of…

Core-structure conjecture. Under these hypotheses, every vertex incident with more than linearly many hyperedges shares a second common vertex with all those hyperedges.

Khanna–Putterman–Sudan conjecture. For their notion of CSP sparsifiability, the dependence on the number of variables is always a polynomial with an integral exponent.

Carbonnel's conjecture. The non-redundancy of any CSP is approximately an upper bound on the kernelization of that CSP.

Let $\pi$ be a distribution over $\Lambda_{k,r}$ and let $H_n(\pi,k,m)$ be the associated random uniquely extendable constraint system. Suppose that either $k\geq 4$ and…

Let $\pi$ be a distribution over $\Lambda_{k,r}$, and let $H_n(\pi,k,m)$ be the associated random uniquely extendable constraint system. Weakened-support conjecture. Theorem should…

Let $G$ be a finite group of order at least two, and let $H_n(\pi,k,m)$ be the random uniquely extendable constraint system arising from the group-equation model described in the s…

Let $k\geq 3$, and let $\mu$ be a distribution over the set $\Lambda_{k,r}$ of $k$-ary uniquely extendable constraint functions. Suppose that, if $k\geq 4$, every function in…