Network Satisfaction for Symmetric Relation Algebras with a Flexible Atom
Authors: Manuel Bodirsky, Simon Knäuer6218-6226
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We provide a complete classification for the case that A is symmetric and has a flexible atom; the problem is in this case NP-complete or in P. If a finite integral relation algebra has a flexible atom, then it has a normal representation B. We can then study the computational complexity of the network satisfaction problem of A using the universal-algebraic approach, via an analysis of the polymorphisms of B. We also use a Ramsey-type result of Neˇsetˇril and R odl and a complexity dichotomy result of Bulatov for conservative finite-domain constraint satisfaction problems. |
| Researcher Affiliation | Academia | Manuel Bodirsky, Simon Kn auer Institut f ur Algebra, TU Dresden, 01062 Dresden, Germany |
| Pseudocode | No | The paper does not contain structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper states that detailed proofs can be found on arXiv (Bodirsky and Kn auer 2020b), but it does not mention providing access to source code for any described methodology. |
| Open Datasets | No | As a theoretical paper, it does not involve training models on datasets, and therefore no dataset availability information is provided. |
| Dataset Splits | No | As a theoretical paper, it does not involve data splits for validation, and therefore no validation split information is provided. |
| Hardware Specification | No | The paper is theoretical and does not describe computational experiments, thus no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and does not describe computational experiments, thus no specific software dependencies with version numbers are provided. |
| Experiment Setup | No | The paper is theoretical and does not describe computational experiments, thus no experimental setup details like hyperparameters or training configurations are provided. |