Infinite-domain CSP dichotomy conjecture

About 1 year old · traced to

Let B\mathfrak{B} be a first-order reduct of a finitely bounded homogeneous structure in a finite relational signature. The constraint satisfaction problem CSP⁡(B)\operatorname{CSP}(\mathfrak{B}) asks whether a finite input structure admits a homomorphism to B\mathfrak{B}. Infinite-domain CSP dichotomy conjecture. The problem CSP⁡(B)\operatorname{CSP}(\mathfrak{B}) is either in P\mathbf{P} or is NP\mathbf{NP}-complete. This extends the finite-domain CSP dichotomy to the indicated class of infinite-domain templates; the source presents it as open and attributes it to earlier work.

References

Primary source

Bertalan Bodor, “Structures with not too fast unlabelled growth”, arXiv:2507.16985 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.