Fractional-polymorphism classification conjecture for homogeneous reducts
Fractional-polymorphism classification conjecture for homogeneous reducts
Let be a valued structure with finite signature such that
for some reduct of a countable finitely bounded homogeneous structure. A pp-construction is the primitive-positive construction notion used in the paper, and denotes the valued constraint satisfaction problem for .
Fractional-polymorphism classification conjecture. If has no pp-construction in , then is in .
Otherwise, the source states that 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.