Near Unanimity Constraints Have Bounded Pathwidth Duality

Near Unanimity Constraints Have Bounded Pathwidth Duality
复制标题

近乎一致的约束限制了路径宽度对偶性

DOI：
--
复制
发表时间：
2012
期刊：
2012 27th Annual IEEE Symposium on Logic in Computer Science
影响因子：
--
通讯作者：
R. Willard
R. Willard
中科院分区：
--
文献类型：
--
作者：
L. Barto;M. Kozik;R. Willard

文献摘要

被引文献

相似文献

我们证明了如果有限关系结构具有接近一致的多态，则以该结构为固定模板的约束满足问题具有有界路宽对偶，从而将问题置于不确定的对数空间中。这推广了Dalmau和Krokhin关于多数多态现象的相似结果，并进一步支持了Larose和Tesson提出的一个猜想。
We show that if a finite relational structure has a near unanimity polymorphism, then the constraint satisfaction problem with that structure as its fixed template has bounded pathwidth duality, putting the problem in nondeterministic logspace. This generalizes the analogous result of Dalmau and Krokhin for majority polymorphisms and lends further support to a conjecture suggested by Larose and Tesson.