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; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1]
Semiring Reasoning Frameworks in AI and Their Computational Complexity
Authors: Thomas Eiter, Rafael Kiesel
JAIR 2023 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this work, we characterize the latter by NP(R), a novel generalization of NP over semiring R, and obtain NP(R)-completeness results for a selection of semiring frameworks. To obtain more tangible insights into the hardness of NP(R), we link it to well-known complexity classes from the literature. Interestingly, we manage to connect the computational hardness to properties of the semiring. We introduce Semiring Turing Machines and show that SAT(R), SCSPs, AMC, weighted first-order formula evaluation over R, as well as some other problems are NP(R)-complete for every semiring R, where NP(R) is a novel analog of NP over semirings. |
| Researcher Affiliation | Academia | Thomas Eiter EMAIL Rafael Kiesel EMAIL Knowledge Based Systems Group Institute of Logic and Computation Vienna University of Technology (TU Wien) Favoritenstraße 9-11 1040 Vienna, Austria |
| Pseudocode | Yes | Algorithm 1 An SRTM algorithm for SAT(R) Input A ΣBF α over semiring R and an interpretation I. Output JαKR(I). 1: function Eval R(α, I) 2: switch α do 3: case α = k: 4: transition with k 5: case α = l, l {v, v}: 6: if l I then: 7: transition with e 8: else: 9: transition with e 10: case α = α1 + α2: 11: Guess i {1, 2} 12: Execute Eval R(αi, I) 13: case α = α1 α2: 14: Execute Eval R(α1, I) 15: Execute Eval R(α2, I) 16: case α = Σvα : 17: Guess I {I \{ v} {v}, I \{v} { v}} 18: Execute Eval R(α , I ) |
| Open Source Code | No | No explicit statement about code release or links to source code repositories for the methodology described in this paper were found. The paper discusses existing implementations like Prob Log, aspmc, and Prov SQL, but these are external tools or prior work, not code released for this specific research. |
| Open Datasets | No | The paper is theoretical, focusing on complexity analysis and proofs. It does not conduct empirical experiments with datasets. Mentions of 'data annotated with semiring values' and 'relational databases' are in a theoretical context and do not refer to specific open datasets used in this research. |
| Dataset Splits | No | The paper presents theoretical research on computational complexity and does not involve empirical experiments using datasets, therefore no dataset splits are discussed. |
| Hardware Specification | No | The paper focuses on theoretical computer science, defining abstract computational models and complexity classes. It does not describe any empirical experiments, and therefore no specific hardware specifications are mentioned for running experiments. |
| Software Dependencies | No | The paper is theoretical and discusses abstract computational models and complexity. It does not provide details of software dependencies with version numbers for the work presented, as it does not involve empirical implementation or experimentation. |
| Experiment Setup | No | This paper is entirely theoretical, presenting definitions, theorems, and proofs related to computational complexity. It does not describe any empirical experiments, and therefore, no experimental setup details, hyperparameters, or training configurations are provided. |