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 [1].
Probabilistic Inference in Credal Networks: New Complexity Results
Authors: D. D. Maua, C. P. de Campos, A. Benavoli, A. Antonucci
JAIR 2014 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we study inferential complexity under the concepts of epistemic irrelevance and strong independence. We show that inferences under strong independence are NP-hard even in trees with binary variables except for a single ternary one. We prove that under epistemic irrelevance the polynomial-time complexity of inferences in credal trees is not likely to extend to more general models (e.g., singly connected topologies). These results clearly distinguish networks that admit efficient inferences and those where inferences are most likely hard, and settle several open questions regarding their computational complexity. |
| Researcher Affiliation | Academia | Denis Deratani Mau a EMAIL Escola Polit ecnica, Universidade de S ao Paulo Av. Prof. Luciano Gualberto, travessa 3, 380 S ao Paulo, 05508-010 Brazil; Cassio Polpo de Campos EMAIL Alessio Benavoli EMAIL Alessandro Antonucci EMAIL Istituto Dalle Molle di Studi sull Intelligenza Artificiale Galleria 2 Manno, 6928 Switzerland |
| Pseudocode | No | The paper primarily presents theoretical results, theorems, and proofs. It does not contain any structured pseudocode or algorithm blocks for its own methodology. |
| Open Source Code | No | The paper does not provide any concrete access to source code (e.g., repository link, explicit code release statement, or code in supplementary materials) for the methodology described. |
| Open Datasets | No | The paper focuses on theoretical complexity results and does not involve experiments on specific datasets. Therefore, no information about publicly available or open datasets is provided. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments that would require dataset splits. Consequently, no information about training/test/validation splits is provided. |
| Hardware Specification | No | The paper discusses theoretical complexity results and does not describe any computational experiments that would require specific hardware specifications. |
| Software Dependencies | No | The paper focuses on theoretical complexity. It does not mention any specific software or library dependencies with version numbers that would be required to reproduce any experimental results. |
| Experiment Setup | No | The paper presents theoretical complexity results rather than empirical experiments. Therefore, no experimental setup details, such as hyperparameter values or training configurations, are provided. |