2021
Network Satisfaction for Symmetric Relation Algebras with a Flexible Atom
AAAI 2021technical
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-c…