REVIEW 2 cited by
The algebraic dichotomy conjecture for infinite domain Constraint Satisfaction Problems
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
We prove that an $\omega$-categorical core structure primitively positively interprets all finite structures with parameters if and only if some stabilizer of its polymorphism clone has a homomorphism to the clone of projections, and that this happens if and only if its polymorphism clone does not contain operations $\alpha$, $\beta$, $s$ satisfying the identity $\alpha s(x,y,x,z,y,z) \approx \beta s(y,x,z,x,z,y)$. This establishes an algebraic criterion equivalent to the conjectured borderline between P and NP-complete CSPs over reducts of finitely bounded homogenous structures, and accomplishes one of the steps of a proposed strategy for reducing the infinite domain CSP dichotomy conjecture to the finite case. Our theorem is also of independent mathematical interest, characterizing a topological property of any $\omega$-categorical core structure (the existence of a continuous homomorphism of a stabilizer of its polymorphism clone to the projections) in purely algebraic terms (the failure of an identity as above).
Forward citations
Cited by 2 Pith papers
-
New Sufficient Algebraic Conditions for Local Consistency over Homogeneous Structures of Finite Duality
Chains of quasi Jónsson operations imply bounded width and polynomial-time solvability for CSPs over first-order expansions of k-neoliberal structures with finite duality.
-
The Network Satisfaction Problem for Relation Algebras with at most 4 Atoms
Every finite relation algebra with at most four atoms has a network satisfaction problem that is either in P or NP-hard, with the paper determining which.
Discussion (0). Continue with ORCID to comment.