Network Satisfaction for Symmetric Relation Algebras with a Flexible Atom

Authors

  • Manuel Bodirsky TU Dresden
  • Simon Knäuer TU Dresden

Keywords:

Computational Complexity of Reasoning, Constraint Satisfaction

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.

Downloads

Published

2021-05-18

How to Cite

Bodirsky, M., & Knäuer, S. (2021). Network Satisfaction for Symmetric Relation Algebras with a Flexible Atom. Proceedings of the AAAI Conference on Artificial Intelligence, 35(7), 6218-6226. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/16773

Issue

Section

AAAI Technical Track on Knowledge Representation and Reasoning