Recognizing the maximum finite number of solutions
Absolute values and vector inequalities are taken componentwise. Inputs are rational numbers written in binary, the input length counts $n$ and the bit lengths of all entries of $A$ and $b$, and algorithms are deterministic Turing machines. For $A \in \mathbb{Q}^{n \times n}$ and $b \in \mathbb{Q}^n$, $n \ge 1$, let $$\Sigma_+(A, b) = \{x \in \mathbb{R}^n : Ax + |x| = b\}.$$ In each orthant this set is empty or part of an affine subspace, so when it is finite it has at most $2^n$ points. Hladík showed that $b > 0$ whenever $|\Sigma_+(A, b)| = 2^n$, that deciding whether $|\Sigma_+(A, b)| > 2^{n-1}$ is NP-complete, and that whether $|\Sigma_+(A, b)| = 2^n$ can be decided in polynomial time when the spectral radius of $|A|$ is less than $1$.
Problem. Classify the computational complexity of deciding, given $A$ and $b$, whether $|\Sigma_+(A, b)| = 2^n$. In particular, is this decision problem in $\mathsf{P}$, or is it $\mathsf{NP}$-hard or $\mathsf{coNP}$-hard under polynomial-time many-one reductions? There is no promise that $\Sigma_+(A, b)$ is finite; infinite solution sets are negative instances.
Source: Hladík (2026; published online 2025), §2.3 and §7, who asks how hard it is to check whether Ax + |x| = b has 2ⁿ solutions and calls its complexity unknown; the bit model, the treatment of infinite solution sets and the hardness notions are OpenProblemsInNLA's.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- OC
- Keywords
- absolute value equations, OpenProblemsInNLA, piecewise linear systems
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@article{hladik2026,
author = {Hlad{\'\i}k, Milan},
title = {Absolute value equations with $2^n$ solutions},
journal = {Optim. Lett.},
volume = {20},
number = {3},
year = {2026},
pages = {559--575},
doi = {10.1007/s11590-025-02251-z},
}
@misc{openproblemsinnla-av01,
author = {Townsend, Alex},
title = {{AV-01}: Recognizing the maximum finite number of solutions},
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-01/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Resolution claims
For rational $A$ and $b$, the paper gives a polynomial-time test for whether $Ax + |x| = b$ has exactly $2^n$ distinct solutions, using $n + 1$ rational linear-programming feasibility problems. No nonsingularity or spectral-radius promise is required, and infinite solution sets are rejected. The proof characterizes the maximum finite solution count by the geometry of a polytope with paired …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-08 | Needs verification → Solution claimed | clemens-admin | Listed with the record of its solution, unreviewed. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00256, "Recognizing the maximum finite number of solutions", clopen.solutions.