The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom

Autor:	Bodirsky, Manuel, Knäuer, Simon
Rok vydání:	2020
Předmět:	Mathematics - Logic Computer Science - Computational Complexity Computer Science - Logic in Computer Science Mathematics - Rings and Algebras
Zdroj:	Journal of Artificial Intelligence Research (JAIR), 75, 2022
Druh dokumentu:	Working Paper
DOI:	10.1613/jair.1.14195
Popis:	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. Comment: 32 pages, 2 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2008.11943 Zobrazit plný text záznamu View this record from Arxiv