The Network Satisfaction Problem for Relation Algebras with at most 4 Atoms
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911052821692416 |
|---|---|
| author | Bodirsky, Manuel Jahn, Moritz Konečný, Matěj Knäuer, Simon Winkler, Paul |
| author_facet | Bodirsky, Manuel Jahn, Moritz Konečný, Matěj Knäuer, Simon Winkler, Paul |
| contents | Andréka and Maddux classified the relation algebras with at most 3 atoms, and in particular they showed that all of them are representable. Hirsch and Cristiani showed that the network satisfaction problem (NSP) for each of these algebras is in P or NP-hard. There are relation algebras with 4 atoms that are not representable, and there are many results in the literature about representations and non-representability of relation algebras with at most 4 atoms. We extend the result of Hirsch and Cristiani to relation algebras with at most 4 atoms: the NSP is always either in P or NP-hard. To this end, we construct universal, fully universal, or even normal representations for these algebras, whenever possible. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_09324 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Network Satisfaction Problem for Relation Algebras with at most 4 Atoms Bodirsky, Manuel Jahn, Moritz Konečný, Matěj Knäuer, Simon Winkler, Paul Rings and Algebras Computational Complexity Logic Andréka and Maddux classified the relation algebras with at most 3 atoms, and in particular they showed that all of them are representable. Hirsch and Cristiani showed that the network satisfaction problem (NSP) for each of these algebras is in P or NP-hard. There are relation algebras with 4 atoms that are not representable, and there are many results in the literature about representations and non-representability of relation algebras with at most 4 atoms. We extend the result of Hirsch and Cristiani to relation algebras with at most 4 atoms: the NSP is always either in P or NP-hard. To this end, we construct universal, fully universal, or even normal representations for these algebras, whenever possible. |
| title | The Network Satisfaction Problem for Relation Algebras with at most 4 Atoms |
| topic | Rings and Algebras Computational Complexity Logic |
| url | https://arxiv.org/abs/2507.09324 |