Network Satisfaction for Symmetric Relation Algebras with a Flexible Atom.
Research output: Contribution to book/conference proceedings/anthology/report › Conference contribution › Contributed › peer-review
Contributors
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 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 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.
Details
Original language | Undefined |
---|---|
Title of host publication | AAAI |
Pages | 6218-6226 |
Number of pages | 9 |
ISBN (electronic) | 9781713835974 |
Publication status | Published - 2021 |
Peer-reviewed | Yes |
External IDs
Scopus | 85110955943 |
---|---|
ORCID | /0000-0001-8228-3611/work/142241132 |