A polynomial Time Algorithm to Solve The Max-atom Problem

arXiv2106.08854MaRDI QIDQ6370465FDOQ6370465

Authors: Chams Lahlou, Laurent Truffet 

Publication date: 16 June 2021

Abstract: In this paper we consider $m$ ($mgeq1$)conjunctions of Max-atoms that is atoms of the form $max(z,y)+rgeqx$, where the offset $r$ is a real constant and $x,y,z$ are variables. We show that the Max-atom problem (MAP) belongs to $extsfP$. Indeed, we provide an algorithm which solves the MAP in $O(n^6{m}^2+n^4{m}^3+n^2{m}^4)$ operations, where $n$ is the number of variables which compose the max-atoms. As a by-product other problems also known to be in $extsfNPcapextsfco-NP$ are in $extsfP$. P1: the problem to know if a tropical cone is trivial or not. P2: problem of tropical rank of a tropical matrix. P3: parity game problem. P4: scheduling problem with AND/OR precedence constraints. P5: problem on hypergraph (shortest path). P6: problem in model checking and $mu$-calculus.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

This page was built for publication: A polynomial Time Algorithm to Solve The Max-atom Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6370465)