---
res:
  bibo_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 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
    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.@eng'
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Krishnendu
      foaf_name: Chatterjee, Krishnendu
      foaf_surname: Chatterjee
      foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0002-4561-241X
  - foaf_Person:
      foaf_givenName: Ruichen
      foaf_name: Luo, Ruichen
      foaf_surname: Luo
      foaf_workInfoHomepage: http://www.librecat.org/personId=b391db08-1ffe-11ee-8b67-d18ddcfb5a14
  - foaf_Person:
      foaf_givenName: Raimundo J
      foaf_name: Saona Urmeneta, Raimundo J
      foaf_surname: Saona Urmeneta
      foaf_workInfoHomepage: http://www.librecat.org/personId=BD1DF4C4-D767-11E9-B658-BC13E6697425
    orcid: 0000-0001-5103-038X
  - foaf_Person:
      foaf_givenName: Jakub
      foaf_name: Svoboda, Jakub
      foaf_surname: Svoboda
      foaf_workInfoHomepage: http://www.librecat.org/personId=130759D2-D7DD-11E9-87D2-DE0DE6697425
    orcid: 0000-0002-1419-3267
  bibo_doi: 10.1609/aaai.v39i11.33212
  bibo_issue: '11'
  bibo_volume: 39
  dct_date: 2025^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/2159-5399
  - http://id.crossref.org/issn/2374-3468
  dct_language: eng
  dct_publisher: Association for the Advancement of Artificial Intelligence@
  dct_title: 'Linear equations with min and max operators: Computational complexity@'
...