Linear Satisfiability Preserving Assignments
Linear Satisfiability Preserving Assignments
复制标题
DOI：
10.1613/jair.5658
复制
发表时间：
2018-02
期刊：
影响因子：
--
通讯作者：
Kei Kimura;K. Makino
中科院分区：
文献类型：
--
作者：
Kei Kimura;K. Makino
本文研究了约束满足问题的几类可满足性保持赋值。我们特别考虑可固定的、固定的和令人满意的任务。由于一般NP-hard很难找到一个非平凡的（即非空的）可满足性保持赋值，我们引入线性可满足性保持赋值，它由相关向量空间中的多面体锥定义。向量空间由Kullmann引入的实向量赋值的辨识得到。我们考虑任意多面体锥体，其中在文献中只考虑了限制类锥体的autark分配。我们揭示了某些类中的锥作为相关向量集合的凸子集是极大的，这可以看作是Kullmann关于cnf的autark赋值结果的扩展。作为算法结果，我们提出了一种伪多项式时间算法，用于计算给定整数线性系统的线性不固定赋值，这暗示了众所周知的整数线性系统的伪多项式可解性，如双变量每不等式，Horn和q-Horn系统。
In this paper, we study several classes of satisfiability preserving assignments to the constraint satisfaction problem. In particular, we consider fixable, autark and satisfying assignments. Since it is in general NP-hard to find a nontrivial (i.e., nonempty) satisfiability preserving assignment, we introduce linear satisfiability preserving assignments, which are defined by polyhedral cones in an associated vector space. The vector space is obtained by the identification, introduced by Kullmann, of assignments with real vectors. We consider arbitrary polyhedral cones, where only restricted classes of cones for autark assignments are considered in the literature. We reveal that cones in certain classes are maximal as a convex subset of the set of the associated vectors, which can be regarded as extensions of Kullmann's results for autark assignments of CNFs. As algorithmic results, we present a pseudo-polynomial time algorithm that computes a linear fixable assignment for a given integer linear system, which implies the well known pseudo-polynomial solvability for integer linear systems such as two-variable-per-inequality, Horn and q-Horn systems.