2 problems

For a finite domain constraint satisfaction problem (CSP), its natural promise problem consists of pairs of instances for which exactly one instance is a yes-instance, with the tas…

Sandwich conjecture. If $\operatorname{PCSP}(G,H)$ is in P, then there is a possibly infinite graph $S$ such that $G\to S\to H$ and $\operatorname{CSP}(S)$ is in P.