The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom
Abstract
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 fexible 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.
Cite
Text
Bodirsky and Knäuer. "The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom." Journal of Artificial Intelligence Research, 2022. doi:10.1613/JAIR.1.14195Markdown
[Bodirsky and Knäuer. "The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom." Journal of Artificial Intelligence Research, 2022.](https://mlanthology.org/jair/2022/bodirsky2022jair-complexity/) doi:10.1613/JAIR.1.14195BibTeX
@article{bodirsky2022jair-complexity,
title = {{The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom}},
author = {Bodirsky, Manuel and Knäuer, Simon},
journal = {Journal of Artificial Intelligence Research},
year = {2022},
pages = {1701-1744},
doi = {10.1613/JAIR.1.14195},
volume = {75},
url = {https://mlanthology.org/jair/2022/bodirsky2022jair-complexity/}
}