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 upto $1$ condition; and
    (C4) the only min or only max operator 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 \textsc{NP}-complete, whereas with condition C1 only, the problem is in \textsc{UP} $\cap$ \textsc{coUP}.
	Finally, we establish the computational complexity of the decision problem of checking the respective conditions.

Linear Equations with Min and Max Operators: Computational Complexity

Constraint Satisfaction and Optimization 2

technical paper

We are pleased to announce the Thirty-Ninth AAAI Conference on Artificial Intelligence (AAAI-25), which will be held in Philadelphia, Pennsylvania at the Pennsylvania Convention Center from February 25 to March 4, 2025.

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. AAAI-25 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and a range of other activities to be announced.

### [Invited Speakers](https://aaai.org/conference/aaai/aaai-25/aaai-25-invited-speakers/)

Register [here](https://aaai.org/conference/aaai/aaai-25/registration/)

AAAI 2025

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. AAAI-25 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and a range of other activities to be announced.



Raimundo Saona

1

1

Presentations

Linear Equations with Min and Max Operators: Computational Complexity

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES