The pp-construction conjecture for hard finite-domain PCSPs over homogeneous reducts

From papers

Let GG and HH be finite graphs, and let SS be a countably infinite graph that is a reduct of a finitely bounded homogeneous structure. Suppose that

GSH.G\to S\to H.

A primitive-positive, or pp, construction interprets one relational structure in another using primitive-positive formulas.

Pp-construction conjecture. If PCSP(G,H)\operatorname{PCSP}(G,H) is NP-hard, then K3K_3 has a pp-construction in SS.

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.

Progress summary

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

Sources & referencesView supporting material

Primary source

Manuel Bodirsky and Santiago Guzmán-Pro, “The Generic Circular Triangle-Free Graph”, arXiv:2404.12082 (2024).

Solutions 0

No solutions have been posted yet.