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..
Linear Equations with Min and Max Operators: Computational Complexity
Authors: Krishnendu Chatterjee, Ruichen Luo, Raimundo Saona, Jakub Svoboda
AAAI 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | However, the systematic computational complexity study of all the cases has not been explored, which we address in this work. Some highlights of our results are: with conditions C2 and C4, and with conditions C3 and C4, the problem is NP-complete, whereas with condition C1 only, the problem is in UP intersects co UP. Finally, we establish the computational complexity of the decision problem of checking the respective conditions. |
| Researcher Affiliation | Academia | 1Institute of Science and Technology Austria Am Campus 1 Klosterneuburg, 3400 Austria EMAIL, EMAIL, EMAIL, EMAIL |
| Pseudocode | No | The paper describes methods using mathematical definitions, theorems, lemmas, and proofs, without presenting any structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code, providing a repository link, or including code in supplementary materials. |
| Open Datasets | No | The paper is theoretical and analyzes computational complexity. It does not refer to specific datasets with access information for empirical evaluation. |
| Dataset Splits | No | The paper does not present any empirical evaluation on datasets, and therefore, no dataset split information is provided. |
| Hardware Specification | No | The paper focuses on theoretical computational complexity analysis and does not describe any experimental setups or hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not describe any implementation details or software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on computational complexity proofs, not empirical experiments, so no experimental setup details are provided. |