The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory
The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory
复制标题
DOI：
10.1137/s0097539794266766
复制
发表时间：
1998-01-01
影响因子：
1.6
通讯作者：
Vardi, MY
中科院分区：
文献类型：
--
作者：
Feder, T;Vardi, MY
本文从寻找一个表现出二分法的NP的大子类开始。方法是通过句法规定来找到这个子类。虽然该文件没有实现这一目标，但它确实隔离了一类（由指定的问题）“单调一元SNP没有不等式”，这可能会表现出这种二分法。我们证明放置所有这些限制的显示，基本上使用拉德纳定理，即类获得仅使用两个上述三个限制不显示这种二分法。然后，我们来看看这个班级的结构。我们表明，在这个类中的所有问题减少到看似简单的类CSP。我们将CSP分为子类，并试图统一收集所有已知的多时间算法的CSP问题和提取的性能，使CSP问题NP-难。这就是标题的第二部分“通过数据库和群论进行的研究”的用武之地。我们提出了关于这个类的说明，它将以显示二分法结束。
This paper starts with the project of finding a large subclass of NP which exhibits a dichotomy. The approach is to find this subclass via syntactic prescriptions. While the paper does not achieve this goal, it does isolate a class (of problems specified by) "monotone monadic SNP without inequality" which may exhibit this dichotomy. We justify the placing of all these restrictions by showing, essentially using Ladner's theorem, that classes obtained by using only two of the above three restrictions do not show this dichotomy. We then explore the structure of this class. We show that all problems in this class reduce to the seemingly simpler class CSP. We divide CSP into subclasses and try to unify the collection of all known polytime algorithms for CSP problems and extract properties that make CSP problems NP-hard. This is where the second part of the title, "a study through Datalog and group theory," comes in. We present conjectures about this class which would end in showing the dichotomy.