9 problems

Let $\Sigma$ be a finite alphabet, let $k\in\mathbb{N}$, and let $\mu$ be a pairwise-connected distribution over $\Sigma^k$ in which every atom has mass at least $\alpha$. A functi…

Let $\mathbb A$ be a first-order reduct of a finitely bounded homogeneous structure. The constraint satisfaction problem of $\mathbb A$ is denoted by…

Infinite-domain tractability conjecture. Such a structure has a polynomial-time tractable CSP unless it admits a primitive positive interpretation of a structure homomorphically eq…

Finitely bounded homogeneous CSP dichotomy conjecture. Exactly one of the following holds: either $\operatorname{Pol}(\mathbb A)$ has a uniformly continuous minion homomorphism to…

A structure is finitely bounded if there exists a finite set $\mathcal F$ of finite structures such that a finite structure $\mathfrak A$ embeds into $\mathfrak B$ if and only if n…

Infinite-domain CSP dichotomy conjecture. One of the following holds: $\mathbb{A}$ satisfies some non-trivial set of h1 identities locally, and $\operatorname{csp}(\mathbb{A})$ is…

Projective-homomorphism dichotomy conjecture. CSPs for such structures should have a complexity dichotomy; moreover, there is a known hardness condition such that every CSP in this…

Barto–Opršal–Pinsker dichotomy conjecture. Exactly one of the following holds:

The tractability frontier conjecture. The constraint satisfaction problem $\operatorname{CSP}(Gamma)$ is tractable if and only if there exist a $4$-ary polymorphism $f$ of $Gamma$…