Linear Equations with Min and Max Operators: Computational Complexity
Authors: Krishnendu Chatterjee, Ruichen Luo, Raimundo Saona, Jakub Svoboda
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | 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. |