relations.

An infinite-domain dichotomy conjecture has been formulated for all CSPs of reducts of finitely bounded homogenous structures, stating that the CSP of such a structure is in P if and only if its polymorphism clone is equationally non-trivial, and NP-hard otherwise.

The complexity of such infinite-domain CSPs as well as of other generalisations (Valued CSPs, Quantified CSPs, Promise CSPs) is still an area of active research.

Every CSP can also be considered as a conjunctive query

1.Previous
3.Next