Hardness of Network Satisfaction for Relation Algebras with Normal Representations

Manuel Bodirsky, Simon Knäuer

We study the computational complexity of the general network satisfaction problem for a finite relation algebra $A$ with a normal representation $B$. If $B$ contains a non-trivial…