Quantified Constraint Satisfaction and 2-Semilattice Polymorphisms
Quantified Constraint Satisfaction and 2-Semilattice Polymorphisms
复制标题
量化约束满足和2-半格多态性
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Hubie Chen
中科院分区：
文献类型：
--
作者：
Hubie Chen
量化约束满足问题（QCSP）是约束满足问题（CSP）的一个自然而有用的推广，其中允许变量的全称量化和存在量化。由于CSP和QCSP通常是难以处理的，因此很多工作都是针对识别这些问题在多项式时间内可处理的限制情况。本文研究了QCSP具有2-半格多态性的限制情况。我们证明了2-半格多态性的一个完全分类，证明了每一个都引起了一个在多项式时间内可处理的QCSP或coNP-hard的情况。
The quantified constraint satisfaction problem (QCSP) is a natural and useful generalization of the constraint satisfaction problem (CSP) in which both universal and existential quantification of variables is permitted. Because the CSP and QCSP are in general intractable, much effort has been directed towards identifying restricted cases of these problems that are tractable in polynomial time. In this paper, we investigate restricted cases of the QCSP having 2-semilattice polymorphisms. We prove a complete classification of 2-semilattice polymorphisms, demonstrating that each gives rise to a case of the QCSP that is either tractable in polynomial time, or coNP-hard.