{"id":"db6aba29-da4e-4c4d-ae59-1397a4a3bb8d","arxiv_id":"2412.12228","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper gives the full complexity landscape for min-max linear equations, with NP-completeness for several subclasses, UP∩coUP when a halting condition holds, and PTIME for a stochastic-game subclass.","lead":"Linear equations with min and max operators cover many optimization problems, from stochastic games to neural network verification. This paper maps exactly how hard these equations are to solve under every combination of four natural restrictions.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 6's proof uses an unproved continuity claim: the inclusion M(α′)⊆M(α;α′) presupposes the continuity of x(α) that it is meant to establish, leaving the UP∩coUP upper bound and all downstream C1 results not rigorously justified as written.","rationale":"The reader's weakest assumption identifies the same load-bearing concern: the continuity claim in Lemma 6 is genuinely the engine of the uniqueness theorem, and the proof's inclusion M(α′)⊆M(α;α′) is asserted without justification and appears to presuppose the very continuity it is meant to prove. The rest of the paper is largely coherent: the NP-hardness reductions (Lemmas 4 and 5), the linear-programming argument conditional on uniqueness (Theorem 4), and the condition-checking reductions are plausible and well-structured. The paper's own examples show that classical monotonicity and minimax-equality tools fail under C1 alone, so the gap cannot be closed by citing Condon-style arguments. Because the reader already flagged this issue and assigned CONDITIONAL, my stress-test does not move the verdict; the paper should remain conditional pending a complete proof of Lemma 6 or a replacement argument establishing uniqueness under C1.","tokens_in":15899,"tokens_out":19374,"duration_ms":188346,"concrete_test":"Prove or disprove the continuity claim independently of Lemma 6. Concretely: for each α, write the finite active-set family M(α); show that for every ε>0 there is δ>0 such that for |α′−α|<δ, M(α′)⊆M(α;α′), using only the invertibility of I−M for M∈conv(Q) (condition C1) and a uniform bound on (I−M(α))^{-1}, not the continuity of x(α). If the inclusion is false, exhibit an α and α′ with a choice active at x(α′) but strictly inactive at x(α); that falsifies the proof as written. Alternatively, run an exhaustive rational search over LEMMs with n≤4 variables, coefficients with denominator at most 4, satisfying C1 via spectral-radius checks, looking for two distinct feasible solutions; a counterexample would refute Lemma 6.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4.3, Lemma 6: the uniqueness proof under C1 proceeds by induction and a homotopy on the last min/max variable. For the reduced systems with x_{m+1}=αx_i+(1−α)x_j, the induction hypothesis gives unique solutions x(α). The proof claims α↦x(α) is continuous, and to prove it asserts that for α′ near α, every active matrix M(α′) at x(α′) belongs to M(α;α′), the set obtained by perturbing a matrix that is active at x(α). This inclusion is not established. It requires that a choice selected at x(α′) was already selected at x(α); this is a stability-of-active-set statement that is equivalent to the continuity being proved. Without it, the bound on |x(α′)−x(α)| by a supremum over M∈M(α) has no basis, and the intermediate-value conclusion x(α*)_i=x(α*)_j is unsupported. The gap is load-bearing: Lemma 6 is used to prove Theorem 2 (UP∩coUP), Theorem 4 (PTIME under {C1,C2,C4}), and the only-if direction of Lemma 9 (PTIME condition checking for {C1,C2}). If the uniqueness theorem is not repaired—e.g., by a joint-spectral-radius/degree-theoretic argument or an explicit perturbation lemma for active sets—the central classification's upper bounds are not proved as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":16188,"tokens_out":12126,"duration_ms":111205,"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":[{"comment":"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).","section":"§4.3, Lemma 6"},{"comment":"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.","section":"§4.4, Lemma 7"},{"comment":"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.","section":"§5, Theorem 9"}],"minor_comments":[{"comment":"There is a typo: \"oerator\" should be \"operator\".","section":"Abstract"},{"comment":"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.","section":"Appendix A.2, Lemma 4 proof"},{"comment":"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.","section":"§4.3, Lemma 6 proof"},{"comment":"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.","section":"Theorem 2"},{"comment":"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.","section":"Appendix A.4, Lemma 7 proof"}],"recommendation":"major_revision","confidential_remarks":"The paper presents an appealing classification and the lower-bound reductions are convincing. The main obstacle is the uniqueness lemma (Lemma 6), whose proof contains a genuine circularity at the continuity step; this is fixable in principle but requires a real argument, not just a sentence. The missing proofs for Lemma 7 and Theorem 9 are also more than cosmetic, since they support stated theorems. I would encourage the editor to seek a revision that supplies these missing proofs. If the uniqueness theorem turns out to be false, the UP∩coUP and PTIME upper bounds collapse, so the revision should be refereed carefully."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things up front. This paper gives the first systematic complexity map for LEMM under all subsets of conditions C1–C4, and that map is worth having. The NP-hardness reductions from partition are clean, the counterexamples showing that monotonicity and minimax equality fail under C1 alone are genuinely illuminating, and the equivalence results give a tidy picture. The condition-checking side is also useful, especially the LP formulation for {C1,C2}.\n\nThe soft spot is real and load-bearing. Lemma 6 claims uniqueness of solutions under C1 alone; the proof works by homotopy on the last min/max variable, with x(α) the unique solution of the reduced system. To prove α↦x(α) is continuous, the proof asserts that for α′ near α, M(α′) ⊆ M(α;α′). That inclusion says any min/max choice selected at x(α′) was already selected at x(α). That is an active-set stability statement, which is essentially the continuity being proved. It is not established, and without it the subsequent bound on |x(α′)−x(α)| has no basis. This is not a cosmetic gap: Lemma 6 is used directly in Theorem 2 (UP∩coUP), Theorem 4 (PTIME for {C1,C2,C4}), and the only-if direction of Lemma 9. If uniqueness fails, those upper bounds collapse.\n\nA smaller gap: in Lemma 7 the constructed LEMM is asserted to satisfy C1, but the proof never shows it. That may be fixable, but it is another unverified step in the same region.\n\nWhat holds up: the partition reductions are complete; the examples do what they claim; the LP argument in Theorem 4 is fine conditional on uniqueness; the lattice arguments and the condition-checking reductions are sensible. The paper is clearly written and honest about what is new.\n\nWho is this for? People working on stochastic games, min-max optimization, and neural-network verification. I would not cite it in its current form because the central lemma is unproved, but I would send it to a serious referee: the question is important and the gap is plausibly repairable, e.g. via a joint-spectral-radius argument or a direct perturbation lemma for active sets. The right outcome is a major revision that proves Lemma 6 properly, not a desk reject.","headline":"A useful complexity landscape for min-max linear equations, but the main upper bounds rest on an unproved continuity claim in Lemma 6.","tokens_in":16752,"tokens_out":3438,"would_cite":false,"duration_ms":32060,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Every min–max linear equation system's complexity is now classified.","keywords":["linear equations with min and max operators","computational complexity","simple stochastic games","NP-complete","UP ∩ coUP","halting condition","Markov decision processes","unique solution"],"falsifier":"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.","tokens_in":15691,"feed_emoji":"🧮","tokens_out":5044,"duration_ms":41914,"temperature":0.7,"pith_summary":"The paper studies systems of linear equations in which some variables are defined by taking minima or maxima over other variables. It asks, for every subset of four natural restrictions — a halting/stability condition, non-negative coefficients, coefficients summing to at most one, and using only one type of operator — how hard it is to decide whether some coordinate of a solution lies below a threshold. The answer is a complete classification: without the stability condition the problem is NP-complete, with stability alone it lies in UP∩coUP and is hard for simple stochastic games, and with stability plus non-negative coefficients it becomes polynomial-time solvable. The load-bearing result is that the stability condition alone already forces a unique solution, which then serves as a unique certificate for both yes and no answers.","feed_headline":"Min–max equation systems fully classified by complexity","feed_subtitle":"NP-complete without the stability condition, in UP∩coUP with it, PTIME for stable nonnegative systems.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the prior result that under C2 and C3 the LEMM decision problem is in NP∩coNP and that C2 and C3 imply C1, anchoring the classical stochastic-game row of the classification.","marker":"Condon 1992"},{"why":"Provides the UP∩coUP bound for simple stochastic games that the paper extends to condition C1 alone.","marker":"Chatterjee and Fijalkow 2011"},{"why":"Supplies the NP-completeness of the partition problem, which is the source of the NP-hardness reductions for {C2,C4} and {C3,C4}.","marker":"Garey and Johnson 1979"},{"why":"Gives the polynomial-time algorithm for checking condition C1 in the presence of C2 and C3, which the paper generalizes to checking C1 with C2.","marker":"Baier and Katoen 2008"}],"fun_headline_variants":["Min-max equations: full complexity map now known","NP-complete without halting condition, PTIME with it","All 16 min-max equation classes pinned down","Stable min-max systems solved in polynomial time"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Min-max equations: full complexity map now known","NP-complete without halting condition, PTIME with it","All 16 min-max equation classes pinned down","Stable min-max systems solved in polynomial time"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00069,"raw_usage":{"total_tokens":3112,"prompt_tokens":917,"completion_tokens":2195,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":533,"completion_tokens_details":{"reasoning_tokens":2133}},"tokens_in":533,"tokens_out":2195,"duration_ms":15982,"temperature":1.0,"reasoning_tokens":2133,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T14:41:03.629717+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the prior result that under C2 and C3 the LEMM decision problem is in NP∩coNP and that C2 and C3 imply C1, anchoring the classical stochastic-game row of the classification."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the UP∩coUP bound for simple stochastic games that the paper extends to condition C1 alone."}],"review_version":1}