Hardness of Network Satisfaction for Relation Algebras with Normal Representations
share
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 equivalence relation with a finite number of equivalence classes, then the network satisfaction problem for A is NP-hard. As a second result, we prove hardness if B has domain size at least three and contains no non-trivial equivalence relations but a symmetric atom a with a forbidden triple (a,a,a), that is, a ≰a ∘ a. We illustrate how to apply our conditions on two small relation algebras.
READ FULL TEXT