论文标题
具有灵活原子的对称关系代数的网络满意度问题的复杂性
The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom
论文作者
论文摘要
罗宾·赫希（Robin Hirsch）于1996年提出的“真正的复杂性问题”：对所有有限关系代数A的网络满意度问题的计算复杂性进行分类。我们为A是对称的情况并具有灵活的原子提供了完整的分类；在这种情况下，问题是NP完成或在P中。分类任务可以简化为A是积分的情况。如果有限的积分关系代数具有灵活的原子，则它具有正常的表示。然后，我们可以通过分析B的多态性来研究A网络满意度问题的计算复杂性。
Robin Hirsch posed in 1996 the 'Really Big Complexity Problem': classify the computational complexity of the network satisfaction problem for all finite relation algebras A. We provide a complete classification for the case that A is symmetric and has a flexible atom; in this case, the problem is NP-complete or in P. The classification task can be reduced to the case where A is integral. If a finite integral relation algebra has a flexible atom, then it has a normal representation B. We can then study the computational complexity of the network satisfaction problem of A using the universal-algebraic approach, via an analysis of the polymorphisms of B. We also use a Ramsey-type result of Nešetřil and Rödl and a complexity dichotomy result of Bulatov for conservative finite-domain constraint satisfaction problems.
