研究带min/max的线性方程组的计算复杂性，揭示不同条件下问题的难易程度。
Linear Equations with Min and Max Operators: Computational Complexity
- 分析含min/max算子的线性方程组在多种约束下的求解机制。
- 证明在特定条件下问题为NP完全，在另一条件下属于UP ∩ coUP。
- 适用于算法理论、博弈论和自动推理领域的研究者。
我们研究一类由含min和max算子的线性方程组定义的优化问题。该类问题在以往研究中受限于若干条件：(C1) 停止或稳定条件；(C2) 非负系数条件；(C3) 系数和为1条件；(C4) 仅含min或仅含max算子条件。文献中的经典结果多聚焦于特例：如轮换随机博弈对应条件C2和C3；马尔可夫决策过程对应条件C2、C3和C4。然而，各类条件组合下的系统性复杂性研究尚未展开，本文填补了这一空白。主要成果包括：在条件C2与C4同时满足时，问题为NP完全；在条件C3与C4同时满足时，问题也为NP完全；而仅满足条件C1时，问题属于UP ∩ coUP。最后，我们还确定了验证各条件成立性的决策问题的计算复杂度。
原文摘要 · Abstract (English)
We consider a class of optimization problems defined by a system of linear equations with min and max operators. This class of optimization problems has been studied under restrictive conditions, such as, (C1) the halting or stability condition; (C2) the non-negative coefficients condition; (C3) the sum up to 1 condition; and (C4) the only min or only max oerator condition. Several seminal results in the literature focus on special cases. For example, turn-based stochastic games correspond to conditions C2 and C3; and Markov decision process to conditions C2, C3, and C4. 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 coUP. Finally, we establish the computational complexity of the decision problem of checking the respective conditions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。