Network Satisfaction Problems Solved by k-Consistency
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911191292444672 |
|---|---|
| author | Bodirsky, Manuel Knäuer, Simon |
| author_facet | Bodirsky, Manuel Knäuer, Simon |
| contents | We show that the problem of deciding for a given finite relation algebra A whether the network satisfaction problem for A can be solved by the k-consistency procedure, for some natural number k, is undecidable. For the important class of finite relation algebras A with a normal representation, however, the decidability of this problem remains open. We show that if A is symmetric and has a flexible atom, then the question whether NSP(A) can be solved by k-consistency, for some natural number k, is decidable (even in polynomial time in the number of atoms of A). This result follows from a more general sufficient condition for the correctness of the k-consistency procedure for finite symmetric relation algebras. In our proof we make use of a result of Alexandr Kazda about finite binary conservative structures. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_12871 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Network Satisfaction Problems Solved by k-Consistency Bodirsky, Manuel Knäuer, Simon Logic Computational Complexity Logic in Computer Science Rings and Algebras We show that the problem of deciding for a given finite relation algebra A whether the network satisfaction problem for A can be solved by the k-consistency procedure, for some natural number k, is undecidable. For the important class of finite relation algebras A with a normal representation, however, the decidability of this problem remains open. We show that if A is symmetric and has a flexible atom, then the question whether NSP(A) can be solved by k-consistency, for some natural number k, is decidable (even in polynomial time in the number of atoms of A). This result follows from a more general sufficient condition for the correctness of the k-consistency procedure for finite symmetric relation algebras. In our proof we make use of a result of Alexandr Kazda about finite binary conservative structures. |
| title | Network Satisfaction Problems Solved by k-Consistency |
| topic | Logic Computational Complexity Logic in Computer Science Rings and Algebras |
| url | https://arxiv.org/abs/2304.12871 |