The equivalence of two dichotomy conjectures for infinite domain constraint satisfaction problems
The equivalence of two dichotomy conjectures for infinite domain constraint satisfaction problems
复制标题
无限域约束满足问题的两个二分猜想的等价性
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
M. Pinsker
中科院分区：
文献类型：
--
作者：
L. Barto;M. Kompatscher;M. Olsák;Trung Van Pham;M. Pinsker
有界齐次结构约简的约束满足问题（CSP）有两种理论：第一种理论认为，当结构是模型完备核时，CSP的易处理性等价于其多态克隆满足一定的非平凡线性单位模外嵌入.第二个猜想，挑战的方法，通过模型完整的核心反射，国家的易处理性是等价的线性身份（没有外部嵌入）满足其多态性克隆，连同自然的一致性，是非平凡的。
There exist two conjectures for constraint satisfaction problems (CSPs) of reducts of finitely bounded homogeneous structures: the first one states that tractability of the CSP of such a structure is, when the structure is a model-complete core, equivalent to its polymorphism clone satisfying a certain non-trivial linear identity modulo outer embeddings. The second conjecture, challenging the approach via model-complete cores by reflections, states that tractability is equivalent to the linear identities (without outer embeddings) satisfied by its polymorphisms clone, together with the natural uniformity on it, being non-trivial.
DOI：
10.1090/tran/6937
发表时间：
2017
期刊：
ArXiv
影响因子：
--
作者：
Manuel Bodirsky;Michael Pinsker;András Pongrácz
通讯作者：
András Pongrácz