Robin Hirsch posed in 1996 the Really Big Complexity Problem: classify the computational complexity of the network satisfaction problem for all finite relation algebras $bf A$. We provide a complete classification for the case that $bf A$ is symmetric and has a flexible atom; the problem is in this case NP-complete or in P. If a finite integral relation algebra has a flexible atom, then it has a normal representation $mathfrak{B}$. We can then study the computational complexity of the network satisfaction problem of ${bf A}$ using the universal-algebraic approach, via an analysis of the polymorphisms of $mathfrak{B}$. We also use a Ramsey-type result of Nev{s}etv{r}il and Rodl and a complexity dichotomy result of Bulatov for conservative finite-domain constraint satisfaction problems.
Download