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

About 2 years old · traced to

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

G→S→H.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.

References

Primary source

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

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.