The pp-construction conjecture for hard finite-domain PCSPs over homogeneous reducts
Let and be finite graphs, and let be a countably infinite graph that is a reduct of a finitely bounded homogeneous structure. Suppose that
A primitive-positive, or pp, construction interprets one relational structure in another using primitive-positive formulas.
Pp-construction conjecture. If is NP-hard, then has a pp-construction in .
This proposes a structural explanation for NP-hardness in the indicated sandwich setting. The paper explicitly leaves the assertion as an open problem; it also notes that, if P differs from NP, the preceding tractability conjecture would imply it.
References
Primary source
Manuel Bodirsky and Santiago Guzmán-Pro, “The Generic Circular Triangle-Free Graph”, arXiv:2404.12082 (2024).
Progress summary
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.