Polynomial-time solution under the regularity promise
Absolute values are taken componentwise. For $A \in \mathbb{Q}^{n \times n}$, the interval matrix $[A - I_n, A + I_n]$ consists of the matrices $A - \operatorname{diag}(d)$ with $d \in [-1, 1]^n$, and is regular if all of them are nonsingular. Inputs are rational numbers written in binary, the input length $\ell$ counts $n$ and the bit lengths of all entries of $A$ and $b$, and algorithms are deterministic Turing machines. Wu and Li showed that $[A - I_n, A + I_n]$ is regular if and only if $Ax - |x| = b$ has a unique solution for every $b \in \mathbb{R}^n$, and Hladík, Moosaei, Hashemi, Ketabchi and Pardalos deduce from Coxson's theorem on P-matrices that deciding this is co-NP-hard. When the singular values of $A$ exceed $1$, a condition of Mangasarian and Meyer that implies regularity, the solution can be computed in polynomial time. Through the standard reductions between absolute value equations and linear complementarity problems, the problem below is equivalent to asking whether linear complementarity problems whose matrix is promised to be a P-matrix can be solved in polynomial time.
Problem. Is there a deterministic algorithm and a polynomial $p$ such that, for every $n \ge 1$ and all $A \in \mathbb{Q}^{n \times n}$ and $b \in \mathbb{Q}^n$ with $[A - I_n, A + I_n]$ regular, the algorithm outputs the exact rational solution $x$ of $Ax - |x| = b$ within $p(\ell)$ bit operations? The algorithm is given no certificate of regularity, and its behaviour on other inputs is unrestricted.
Source: Stated by OpenProblemsInNLA, after Hladík, Moosaei, Hashemi, Ketabchi and Pardalos (2026), §2.4.2 (first posted as arXiv:2404.06319, 2024); the absolute value equation form of the classical question whether P-matrix linear complementarity problems can be solved in polynomial time.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- OC
- Keywords
- absolute value equations, linear complementarity problems, OpenProblemsInNLA, P-matrices
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@article{hladik2026,
author = {Hlad{\'\i}k, Milan and Moosaei, Hossein and Hashemi, Fakhrodin and Ketabchi, Saeed and Pardalos, Panos M.},
title = {An overview of absolute value equations: from theory to solution methods and challenges},
journal = {Comput. Optim. Appl.},
volume = {93},
number = {1},
year = {2026},
pages = {435--488},
doi = {10.1007/s10589-025-00717-5},
eprint = {2404.06319},
archivePrefix = {arXiv},
}
@article{wu2018,
author = {Wu, Shi-Liang and Li, Cui-Xia},
title = {The unique solution of the absolute value equations},
journal = {Appl. Math. Lett.},
volume = {76},
year = {2018},
pages = {195--200},
doi = {10.1016/j.aml.2017.08.012},
}
@article{coxson1994,
author = {Coxson, Gregory E.},
title = {The {P}-matrix problem is co-{NP}-complete},
journal = {Math. Program.},
volume = {64},
number = {1--3},
year = {1994},
pages = {173--178},
doi = {10.1007/BF01582570},
}
@article{mangasarian2006,
author = {Mangasarian, Olvi L. and Meyer, Robert R.},
title = {Absolute value equations},
journal = {Linear Algebra Appl.},
volume = {419},
number = {2--3},
year = {2006},
pages = {359--367},
doi = {10.1016/j.laa.2006.05.004},
}
@inproceedings{borzechowski2024,
author = {Borzechowski, Michaela and Fearnley, John and Gordon, Spencer and Savani, Rahul and Schnider, Patrick and Weber, Simon},
title = {Two Choices Are Enough for {P-LCPs}, {USOs}, and Colorful Tangents},
booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
series = {LIPIcs},
volume = {297},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
year = {2024},
pages = {32:1--32:18},
doi = {10.4230/LIPIcs.ICALP.2024.32},
eprint = {2402.07683},
archivePrefix = {arXiv},
}
@misc{openproblemsinnla-av03,
author = {Townsend, Alex},
title = {{AV-03}: Polynomial-time solution under the regularity promise},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/intervals-and-absolute-value-equations/AV-03/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Resolution claims
For rational $A$ and $b$ such that every matrix $A-\operatorname{diag}(d)$, $d\in[-1,1]^n$, is nonsingular, the note gives a deterministic algorithm of polynomial bit complexity that computes the exact solution of $Ax-|x|=b$ when $A$ is lower Hessenberg, including zero superdiagonal entries and zero solution coordinates. Taking the first coordinate as a parameter, the first $n-1$ equations determine the others by a shooting …
For rational $A$ and $b$ such that every $A-\operatorname{diag}(d)$, $d\in[-1,1]^n$, is nonsingular, the note gives a deterministic algorithm of polynomial bit complexity that computes the exact solution of $Ax-|x|=b$ when the leading $(n-1)\times(n-1)$ block of $A$ is lower triangular with diagonal entries of modulus greater than one; the last row and column are arbitrary. Taking the last coordinate as a …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-08 | Open → Partially resolved | The registry's curators | Exact scalar shooting for a structured subclass v1 recorded from OpenProblemsInNLA @ eb7c9d6, AV-03/result.md. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00196, "Polynomial-time solution under the regularity promise", clopen.solutions.