Name
Abstract | ||
|---|---|---|
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 \not\leq a \circ a$. We illustrate how to apply our conditions on two small relation algebras. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1007/978-3-030-43520-2_3 | RAMiCS |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Manuel Bodirsky | 1 | 644 | 54.63 |
| Simon Knäuer | 2 | 0 | 0.68 |