Fractional-polymorphism classification conjecture for homogeneous reducts

Let Γ\Gamma be a valued structure with finite signature such that

Aut(Γ)=Aut(B)\operatorname{Aut}(\Gamma)=\operatorname{Aut}(\mathfrak{B})

for some reduct B\mathfrak{B} of a countable finitely bounded homogeneous structure. A pp-construction is the primitive-positive construction notion used in the paper, and VCSP(Γ)\operatorname{VCSP}(\Gamma) denotes the valued constraint satisfaction problem for Γ\Gamma.

Fractional-polymorphism classification conjecture. If ({0,1};OIT)(\{0,1\};\operatorname{OIT}) has no pp-construction in Γ\Gamma, then VCSP(Γ)\operatorname{VCSP}(\Gamma) is in P\operatorname{P}.

Otherwise, the source states that VCSP(Γ)\operatorname{VCSP}(\Gamma) is already known to be NP-complete. Thus the conjecture would give a full P-versus-NP-complete classification for finite-signature valued structures with the stated homogeneous-reduct automorphism group.

Sources & referencesView supporting material

Primary source

Manuel Bodirsky, Žaneta Semanišinová and Carsten Lutz, “The Complexity of Resilience Problems via Valued Constraint Satisfaction”, arXiv:2309.15654 (2025).

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.