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\v{s}et\v{r}il and R\"odl and a complexity dichotomy result of Bulatov for conservative finite-domain constraint satisfaction problems.
翻译:Robin Hirsch于1996年提出了“非常大的复杂性问题 ” : 对所有有限关系代数 A 的网络满意度的计算复杂性进行分类。 我们为A是对称和具有灵活原子的情况提供了完整的分类; 在此情况下, 问题为NP- 完成或 P 。 分类任务可以缩到 A 是有机体的情况。 如果一个有限的整体关系代数具有灵活的原子, 那么它有一个正常的代号 B 。 然后, 我们可以使用通用的代数法, 通过分析 B 的多形态, 来研究 A 网络满意度的计算复杂性。 我们还使用 Ne\v{ et\ v{r}il 和 R\\'odl 的Ramsey 类结果, 以及 Bulatov 的复杂二分立结果, 来研究保守的有限制约满足问题。