Content deleted Content added
Citation bot (talk | contribs) Altered journal. Add: isbn, volume. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 86/492 |
Citation bot (talk | contribs) Added hdl. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 144/892 |
||
Line 56:
Most classes of CSPs that are known to be tractable are those where the [[hypergraph]] of constraints has bounded [[treewidth]],<ref>{{Cite journal |last1=Barto |first1=Libor |last2=Kozik |first2=Marcin |date=2014-01-01 |title=Constraint Satisfaction Problems Solvable by Local Consistency Methods |url=https://doi.org/10.1145/2556646 |journal=J. ACM |volume=61 |issue=1 |pages=3:1–3:19 |doi=10.1145/2556646 |issn=0004-5411}}</ref> or where the constraints have arbitrary form but there exist equationally non-trivial polymorphisms of the set of constraint relations.<ref>{{Cite book |last=Bodirsky |first=Manuel |url=https://www.cambridge.org/core/books/complexity-of-infinitedomain-constraint-satisfaction/8E6E86C8F8C5C534440266EFB9E584D3 |title=Complexity of Infinite-Domain Constraint Satisfaction |date=2021 |publisher=Cambridge University Press |isbn=978-1-107-04284-1 |series=Lecture Notes in Logic |___location=Cambridge}}</ref>
An ''infinite-___domain dichotomy conjecture''<ref>{{Cite journal |last1=Bodirsky |first1=Manuel |last2=Pinsker |first2=Michael |last3=Pongrácz |first3=András |date=March 2021 |title=Projective Clone Homomorphisms |url=https://www.cambridge.org/core/journals/journal-of-symbolic-logic/article/abs/projective-clone-homomorphisms/3654D0B62D3C45DF6DBD93DDC57B8B02 |journal=The Journal of Symbolic Logic |language=en |volume=86 |issue=1 |pages=148–161 |doi=10.1017/jsl.2019.23 |issn=0022-4812|arxiv=1409.4601 |hdl=2437/268560 }}</ref> 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 [[Clone (algebra)|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.<ref>{{cite arXiv |last=Pinsker |first=Michael |title=Current Challenges in Infinite-Domain Constraint Satisfaction: Dilemmas of the Infinite Sheep |date=2022-03-31 |class=cs.LO |eprint=2203.17182}}</ref>[https://tu-dresden.de/tu-dresden/newsportal/news/erc-synergy-grant-fuer-pococop-komplexitaet-von-berechnungen?set_language=en][https://www.tuwien.at/tu-wien/aktuelles/news/erc-synergy-grant-die-komplexitaet-von-berechnungen]
| |||