Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Network Satisfaction for Symmetric Relation Algebras with a Flexible Atom
Authors: Manuel Bodirsky, Simon Knäuer6218-6226
AAAI 2021 | Venue PDF | 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. |