Research map / Learning theory and algorithms / Combinatorial and search optimization

Linear Equations with Min and Max Operators: Computational Complexity

AAAI 2025 · Learning theory and algorithms › Combinatorial and search optimization · approach: Structure and complexity of constraint reasoning · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Systematically maps the computational complexity of linear equations with min and max operators (LEMM) under all subsets of four restrictive conditions (halting, non-negative coefficients, sum-up-to-1, min-only/max-only), and of checking those conditions.

Problem

Computational complexity of optimization problems defined by linear equations with min and max operators under restrictive sub-conditions (halting/stability, non-negative coefficients, sum up to 1, single operator type), plus complexity of checking these conditions.

Approach

Gives the complete complexity landscape across all subsets of conditions C1-C4; shows that under only the halting condition (C1) a unique solution still exists via induction and continuity, giving UP ∩ coUP membership, and that C2+C4 and C3+C4 are NP-complete via partition reductions, while checking C1 is coNP-hard.

Key results

• With conditions C2 and C4, and with C3 and C4, the LEMM decision problem is NP-complete.
• Under condition C1 only, the LEMM decision problem is in UP ∩ coUP, via a unique-solution lemma proven by induction and continuity.
• Checking condition C1 is coNP-hard, while checking C1 and C2 (and related conditions) can be done in polynomial time via linear programming.

Surprising findings

• Under C1 alone, monotonicity, the min-max equals max-min property, and solution-from-subsolution all fail, although a unique solution still exists.
• Even under C1, C3, and C4 the problem is as hard as simple stochastic games (SSG-hard).

Limitations

• Purely theoretical; no empirical evaluation or implementation.
• Complexity status of SSG-hard cases remains tied to the open SSG problem (no polynomial algorithm known).

Experimental setup

Builds on: simple stochastic games Markov decision processes partition problem

Closest papers by meaning

• Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexity (ICML 2024 · similarity 0.85)
• The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games (NeurIPS 2025 · similarity 0.84)
• Convergence of $\text{log}(1/\epsilon)$ for Gradient-Based Algorithms in Zero-Sum Games without the Condition Number: A Smoothed Analysis (NeurIPS 2024 · similarity 0.84)
• Finding Simple Proofs for First-Order Optimization (NeurIPS 2026 · similarity 0.84)
• On the Complexity of Finite-Sum Smooth Optimization under the Polyak–Łojasiewicz Condition (ICML 2024 · similarity 0.84)
• Sample complexity of stochastic optimization with integer variables (NeurIPS 2026 · similarity 0.84)