On the Complexity of Sum-of-Products Problems over Semirings
Authors: Thomas Eiter, Rafael Kiesel6304-6311
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We characterize the latter by NP(R), a novel generalization of NP over semiring R, and link it to well-known complexity classes. While NP(R) is unlikely to be contained in FPSPACE(POLY) in general, for a wide range of commutative (resp. in addition idempotent) semirings, there are reductions to #P (resp. NP) and solutions are thus only mildly harder to compute. We finally discuss NP(R)-complete reasoning problems in well-known semiring formalisms, among them Semiring-based Constraint Satisfaction Problems, obtaining new insights into their computational properties. |
| Researcher Affiliation | Academia | Thomas Eiter and Rafael Kiesel Vienna University of Technology Favoritenstrasse 9-11 Vienna 1040 {thomas.eiter,rafael.kiesel}@tuwien.ac.at |
| Pseudocode | Yes | Algorithm 1 An algorithm for weighted formula evaluation. |
| Open Source Code | No | The paper does not provide a statement or link indicating that open-source code for the described methodology is available. |
| Open Datasets | No | The paper focuses on theoretical complexity analysis and does not describe experiments involving datasets for training, validation, or testing. |
| Dataset Splits | No | The paper is theoretical and does not discuss dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe experiments that would require specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not mention specific software dependencies with version numbers for reproducibility. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or system-level training settings. |