REVIEW 3 major objections 5 minor 22 references
Linear Equations with Min and Max Operators: Computational Complexity
T0 review · 3 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read Every min–max linear equation system's complexity is now classified.
desk verdict A useful complexity landscape for min-max linear equations, but the main upper bounds rest on an unproved continuity claim in Lemma 6. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the LEMM — a system of linear equations where the first group of variables equal minima over a set, the next group equal maxima, and the rest are affine in all variables. The machinery that carries the upper bounds is Lemma 6, which asserts that under condition C1 alone every such system has exactly one solution. The proof works by slowly interpolating one operator's choice between its two options, through a parameter α, and using continuity of the resulting solutions to force a crossing point where the two choices agree. This uniqueness turns the single solution into a polynomial-time-verifiable certificate for both YES and NO answers, giving the UP∩coUP bound; it also makes the PTIME bound for {C1,C2,C4} fall out of a linear program.
What would settle it
Find a system satisfying condition C1 for which the map α ↦ x(α) of unique solutions of the interpolated systems is discontinuous at some α, or for which the set-inclusion M(α′) ⊆ M(α;α′) fails for arbitrarily close α′. Such an instance would invalidate the proof of Lemma 6 and would likely break the UP∩coUP upper bound, because the uniqueness certificate would no longer be guaranteed.
Extended reading notes
Core claim
The paper's central claim is a full computational-complexity classification of the LEMM decision problem for all sixteen subsets of conditions C1–C4. The classification has three tiers: NP-complete for the class without the halting condition (except the {C2,C3} row, which inherits the classical simple-stochastic-game bound); UP∩coUP and SSG-hard for the classes that include C1 but not C2 (again with the {C2,C3} exception); and PTIME for the classes that include both C1 and C2. A key component is the proof that condition C1 by itself guarantees existence and uniqueness of the solution, even though the classical monotonicity and minimax-equality properties fail without C2 and C3. The paper also classifies the problem of checking the conditions themselves: checking C1 is coNP-hard, while checking C1 together with C2 can be done in polynomial time via linear programming.
Load-bearing premise
The upper-bound results for condition C1 stand on a continuity claim: as one interpolates between the two choices of a min/max operator, the unique solutions of the modified systems must vary continuously, and that continuity is what forces a crossing point where the original system has a solution.
Editorial extensions
If this is right
- Every LEMM restricted only by the halting condition has a unique solution, so the yes/no decision problem has a unique certificate for each answer; this is what puts the problem in UP∩coUP.
- The NP-completeness for {C2,C4} and {C3,C4} means simple-looking min-only or max-only systems with non-negative or sum-bounded coefficients are already computationally intractable.
- The PTIME result for {C1,C2,C4} extends the classical polynomial-time solvability of Markov decision processes to systems that satisfy stability, non-negative coefficients, and a single operator type, without requiring the stochastic sum condition.
- Because checking the halting condition alone is coNP-hard, any general-purpose algorithm that merely verifies C1 must be able to solve the complement of SAT; checking it together with non-negative coefficients is instead polynomial-time.
Reading between the lines
- The uniqueness-under-C1 theorem suggests that existing algorithms for simple stochastic games, which rely on monotonicity and minimax equality, might be transferable to the wider class {C1} by replacing those properties with a continuity-based argument; the paper does not explore this algorithmic transfer.
- The polynomial-time equivalence between {C1} and {C1,C3,C4} implies that any hardness or algorithm for min-only stable systems carries over to general stable systems; this could simplify future work on condition C1 by letting researchers restrict attention to min-only instances.
- A testable extension would be to check numerically whether the continuity claim in the proof of the key lemma holds for randomly generated C1 systems with rational coefficients; a counterexample would point to a gap in the uniqueness proof as written.
- The NP-completeness of unrestricted LEMM mirrors the NP-completeness of neural-network verification with piecewise-linear activations, so the complexity map here gives a sense of which natural restrictions on the network (e.g., stability, non-negative weights) would move verification into polynomial time.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the decision problem for systems of linear equations with min and max operators (LEMM) under four conditions: C1 (stability/halting), C2 (non-negative coefficients), C3 (sum up to 1), and C4 (only min or only max). The main claimed contribution is a complete complexity classification: NP-complete for condition sets without C1 (except the PTIME row), UP∩coUP and SSG-hard for sets containing C1 but not C2, and PTIME for {C1,C2,C4} and its supersets. The paper also studies the complexity of checking the conditions themselves, proving CONP-hardness for C1 and PTIME for C1 together with C2. The central technical lemma (Lemma 6) asserts that condition C1 alone guarantees existence and uniqueness of solutions, a property that is then used to establish the UP∩coUP upper bound, the PTIME result for {C1,C2,C4}, and the only-if direction of the condition-checking characterization in Lemma 9.
Significance. If the technical gaps are repaired, this would be a significant contribution: it provides a systematic complexity landscape for a natural class of min-max linear systems, unifies and extends earlier results on simple stochastic games and Markov decision processes, and demonstrates that even though classical monotonicity and minimax properties fail under C1 alone, structural results can still be recovered. The counterexamples in Section 4.3 are illuminating, and the NP-hardness reductions in Section 4.2 appear sound. The LP-based PTIME argument in Theorem 4 is clean and would be correct conditional on uniqueness. The condition-checking results in Section 5 are also valuable. However, the proof of the key uniqueness lemma has a load-bearing gap, and several claimed theorem proofs in the appendix are asserted rather than demonstrated.
major comments (3)
- [§4.3, Lemma 6] The proof of continuity of α↦x(α) is not rigorous as written. The crucial assertion is the inclusion M(α′) ⊆ M(α;α′) for α′ near α, which says that every active choice at α′ was already active at α. This is a stability-of-active-sets statement; it is not a consequence of the continuity of the min and max operators alone, and it appears to presuppose the continuity of x(α) that the argument is intended to establish. Without this inclusion, the bound on |x(α_n)−x(α)| by a supremum over M(α;α_n) has no basis, and the intermediate-value conclusion x(α*)_i = x(α*)_j is unsupported. Since Lemma 6 underpins Theorem 2, Theorem 4, and the only-if direction of Lemma 9, the upper-bound results for {C1} and {C1,C2,C4} are not rigorously proved as written. The authors should supply a genuine perturbation/stability argument for the active sets, or an alternative proof of the uniqueness theorem (e.g., via a degree-theoretic or joint-spectral-radius argument).
- [§4.4, Lemma 7] The proof of Lemma 7 in Appendix A.4 asserts the equivalence between solutions of the original LEMM under {C1} and solutions of the constructed LEMM under {C1,C3,C4}, but does not actually prove it. The sentence "Then, x is a solution to (1) if and only if x′ = ... is the solution to (6)" is a claim, not a verification. In particular, the construction with negative and positive copies must be checked in detail: one needs to show that every solution of (1) lifts to a solution of (6), that every solution of (6) restricts to a solution of (1), and that condition C1 is preserved by the construction. Because Lemma 7 is the basis for the claimed polynomial equivalence of the second row of Table 1, this missing proof is load-bearing for that portion of the classification.
- [§5, Theorem 9] The proof of Theorem 9 does not establish the claimed characterization. The appendix defines a reduction from SAT and then states "we have 'condition C1 holds' if and only if 'c1∧...∧cm is unsatisfiable'" without proving either direction. The earlier sentence "Finally, we show that..." is not followed by an argument. Since Corollary 10 and the CONP-hardness results for condition checking depend on this equivalence, the theorem is unproved as written. A complete proof of the reduction's correctness is needed.
minor comments (5)
- [Abstract] There is a typo: "oerator" should be "operator".
- [Appendix A.2, Lemma 4 proof] The proof sets n=2m+1 but then uses q_{2m+2} and x_{2n1+2}; the intended system has n=2m+2. This off-by-one inconsistency should be corrected.
- [§4.3, Lemma 6 proof] The reduction to the case |N(i)|=2 for every min/max variable is asserted "without loss of generality" but not justified; the authors should explain how larger neighborhoods are handled by introducing auxiliary variables, or provide a reference.
- [Theorem 2] For a UP∩coUP certificate, the unique solution must have bit complexity polynomial in the input size. This is not stated; it follows from standard determinant bounds for rational linear systems, but the paper should say so explicitly.
- [Appendix A.4, Lemma 7 proof] In the definition of \bar q_k, the index range "n2 < k ≤ n" should presumably be "n1+n2 < k ≤ n", and the dimensions of the block matrix in the displayed formula appear inconsistent with the resulting vector length. These should be clarified.
Circularity Check
No circularity: central classification is derived from explicit reductions and an independent uniqueness lemma; the Lemma 6 continuity step is a proof gap, not a circular reduction.
full rationale
The paper's derivation chain is self-contained with respect to circularity. The NP-hardness reductions (Lemmas 4 and 5) reduce from Partition and from {C4} respectively by explicit LEMM constructions, and the polynomial-time equivalences (Lemma 7) give explicit variable transformations; none of these define a target quantity in terms of itself or fit a parameter and then relabel it as a prediction. Lemma 6, the key uniqueness result, is proved by induction on the number of min/max variables and does not invoke the theorem it is meant to establish. The only substantive concern is the unproved stability claim in the continuity part of Lemma 6's proof ('By the continuity of linear, min, and max operators, there exists ε > 0 ... we have M(α′)⊆M(α;α′)'): this is a genuine proof gap, because the inclusion is not obviously implied by continuity and seems to presuppose the active-set stability that the argument is trying to establish. However, this is not circularity in the sense of the target result being assumed or being equivalent to an input by construction; it is an omitted justification in an otherwise independent proof. The paper's self-citations (Chatterjee and Fijalkow 2011; Chatterjee et al. 2023) are used for standard external results or contextual comparisons, and the UP∩coUP result under {C1} does not reduce to them. Since no derivation step is equivalent to its own inputs, the circularity score is 0.
Assumptions & free parameters
assumptions (4)
- standard math Spectral radius criterion: if Q^m → 0 then I-Q is invertible and (I-Q)^(-1) = Σ Q^m
- standard math Perron-Frobenius theorem for non-negative matrices
- standard math Linear programming is polynomial-time solvable
- standard math NP-completeness of Partition and SAT
Cite this review
Pith. "Pith review of Linear Equations with Min and Max Operators: Computational Complexity." pith.science (2026). https://pith.science/paper/7SUPK6UQ
@misc{pith2026241212228,
author = {Pith},
title = {Pith review of: Linear Equations with Min and Max Operators: Computational Complexity},
year = {2026},
howpublished = {\url{https://pith.science/paper/7SUPK6UQ}},
note = {Machine review of arXiv:2412.12228}
}
read the original abstract
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.
Figures
Reference graph
Works this paper leans on
-
[1]
, " * write output.state after.block = add.period write newline
ENTRY address archivePrefix author booktitle chapter edition editor eid eprint howpublished institution isbn journal key month note number organization pages publisher school series title type volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.a...
-
[2]
write newline
" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize " " * FUNCT...
-
[3]
Athreya, K. B.; and Ney, P. E. 2004. Branching processes. Courier Corporation
work page 2004
-
[4]
Baier, C.; and Katoen, J.-P. 2008. Principles of model checking. MIT press
2008
-
[5]
Bottou, L. 2010. Large-scale machine learning with stochastic gradient descent. In Proceedings of the 19th International Conference on Computational Statistics (COMPSTAT), 177--186
work page 2010
-
[6]
Chatterjee, K.; and Fijalkow, N. 2011. A reduction from parity games to simple stochastic games. In Proceedings of the Second International Symposium on Games, Automata, Logics and Formal Verification (GandALF), volume 54 of EPTCS , 74--86
work page 2011
-
[7]
Chatterjee, K.; Kafshdar Goharshady, E.; Karrabi, M.; Novotny, P.; and Z ikeli \'c , D. 2024. Solving Long-run Average Reward Robust MDPs via Stochastic Games . In Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence ( IJCAI-24 ) , 6707--6715
work page 2024
-
[8]
Chatterjee, K.; Meggendorfer, T.; Saona, R.; and Svoboda, J. 2023. Faster algorithm for turn-based stochastic games with bounded treewidth. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 4590--4605
work page 2023
Show all 22 references
-
[9]
Condon, A. 1990. On Algorithms for Simple Stochastic Games. Advances in computational complexity theory, 13: 51--72
1990
-
[10]
Condon, A. 1992. The Complexity of Stochastic Games. Information and Computation, 96(2): 203--224
1992
-
[11]
Dantzig, G. B. 2002. Linear programming. Operations research, 50(1): 42--47
2002
-
[12]
R.; and Johnson, D
Garey, M. R.; and Johnson, D. S. 1979. Computers and intractability, volume 174. freeman San Francisco
1979
-
[13]
G \"a rtner, B.; and Matousek, J. 2012. Approximation algorithms and semidefinite programming. Springer Science & Business Media
2012
-
[14]
Goodfellow, I.; Warde-Farley, D.; Mirza, M.; Courville, A.; and Bengio, Y. 2013. Maxout networks. In International conference on machine learning, 1319--1327
2013
-
[15]
A.; and Rothe, J
Hemaspaandra, L. A.; and Rothe, J. 1997. Unambiguous computation: Boolean hierarchies and sparse Turing-complete sets. SIAM Journal on Computing, 26(3): 634--653
1997
-
[16]
L.; Julian, K.; and Kochenderfer, M
Katz, G.; Barrett, C.; Dill, D. L.; Julian, K.; and Kochenderfer, M. J. 2017. Reluplex: An efficient SMT solver for verifying deep neural networks. In Proceedings of the 29th International Conference on Computer Aided Verification (CAV), 97--117
2017
-
[17]
Ludwig, W. 1995. A subexponential randomized algorithm for the simple stochastic game problem. Information and computation, 117(1): 151--155
1995
-
[18]
Markowitz, H. 1952. Portfolio Selection . The Journal of Finance, 7(1): 77
1952
-
[19]
Nesterov, Y. 2013. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media
2013
-
[20]
Puterman, M. L. 2014. Markov Decision Processes : Discrete Stochastic Dynamic Programming . Wiley
2014
-
[21]
Shapley, L. S. 1953. Stochastic Games . Proceedings of the National Academy of Sciences, 39(10): 1095--1100
1953
-
[22]
von Neumann, J.; and Morgenstern, O. 1953. Theory of games and economic behavior. Princeton university press
1953
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.