OP-00265 Partially resolved

Exact solution hulls for tridiagonal interval systems

For $n \ge 1$ let $\mathcal T$ be an $n \times n$ tridiagonal interval matrix and $\mathbf{b}$ an interval vector in $\mathbb{R}^n$, all with rational endpoints: $T_{ij} = 0$ for $|i - j| > 1$, and the other entries of $T$ and the entries of $b$ range independently over given closed intervals. Let $$\Sigma = \{x \in \mathbb{R}^n : Tx = b \text{ for some } T \in \mathcal T \text{ and } b \in \mathbf{b}\}$$ be the united solution set. For general interval matrices, computing the exact interval hull of the solution set is NP-hard, even for regular ones (see Horáček, Hladík and Černý). Horáček, Hladík and Černý state that it is NP-hard also for pentadiagonal interval matrices ($T_{ij} = 0$ for $|i - j| \ge 3$), and show that it is strongly polynomial for bidiagonal ones, assuming, as throughout that section, that the solution set is bounded.

Problem. Is there a deterministic algorithm that, given $\mathcal T$ and $\mathbf{b}$, computes the exact coordinatewise interval hull of $\Sigma$ in time polynomial in the total binary input length? It must report that $\Sigma$ is empty when it is, and otherwise return $$\Big[\inf_{x \in \Sigma} x_i,\ \sup_{x \in \Sigma} x_i\Big], \qquad i = 1, \dots, n,$$ with finite endpoints as exact rationals and infinite endpoints represented explicitly. No regularity is assumed: intervals may contain $0$ and members of $\mathcal T$ may be singular.

Source: Horáček, Hladík and Černý (2017), §1.4.3 of the arXiv version, first posted as arXiv:1602.00349 (2016); again Hladík (2020), §2 of the arXiv version. Stated with explicit input and output conventions, and without assuming regularity, by OpenProblemsInNLA.

Imported from github.com/ajt60gaibb/OpenProblemsInNLA.

Classification

Primary: NA — Numerical Analysis
Secondary: RA
Keywords: interval matrices, linear systems, OpenProblemsInNLA, tridiagonal matrices
Literature checked: Oct. 8, 2026 by clemens-admin

References

@incollection{horacek2017,
  author        = {Hor{\'a}{\v{c}}ek, Jaroslav and Hlad{\'\i}k, Milan and {\v{C}}ern{\'y}, Michal},
  title         = {Interval Linear Algebra and Computational Complexity},
  booktitle     = {Applied and Computational Matrix Analysis},
  editor        = {Bebiano, Nat{\'a}lia},
  series        = {Springer Proc. Math. Stat.},
  volume        = {192},
  publisher     = {Springer},
  address       = {Cham},
  year          = {2017},
  pages         = {37--66},
  doi           = {10.1007/978-3-319-49984-0_3},
  eprint        = {1602.00349},
  archivePrefix = {arXiv},
}
@incollection{hladik2020,
  author        = {Hlad{\'\i}k, Milan},
  title         = {An Overview of Polynomially Computable Characteristics of Special Interval Matrices},
  booktitle     = {Beyond Traditional Probabilistic Data Processing Techniques: Interval, Fuzzy etc. Methods and Their Applications},
  editor        = {Kosheleva, Olga and Shary, Sergey P. and Xiang, Gang and Zapatrin, Roman},
  series        = {Stud. Comput. Intell.},
  volume        = {835},
  publisher     = {Springer},
  address       = {Cham},
  year          = {2020},
  pages         = {295--310},
  doi           = {10.1007/978-3-030-31041-7_16},
  eprint        = {1711.08732},
  archivePrefix = {arXiv},
}
@misc{openproblemsinnla-iv04,
  author       = {Townsend, Alex},
  title        = {{IV-04}: Exact solution hulls for tridiagonal interval systems},
  howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
  year         = {2026},
  url          = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/intervals-and-absolute-value-equations/IV-04/README.md},
  note         = {Read at commit eb7c9d6, 2026-10-07},
}

Resolution claims

Exact tridiagonal interval determinants and solution hulls are NP-hard v1 GitHub ↗

Matthew J. Colbrook

A reduction from PARTITION encodes signed sums of small rational rotation angles in the continuant of a tridiagonal interval matrix. It proves that deciding whether the maximum determinant of a rational tridiagonal interval matrix is at least a rational threshold is NP-complete, and that computing the exact determinant range, and the exact interval hull of the solution set of a …

Partial resolution · not verified · fidelity not established · posted on GitHub 11 Sep 2026

Status history

When	Change	By	Reason
2026-10-08	Open → Partially resolved	The registry's curators	Exact tridiagonal interval determinants and solution hulls are NP-hard v1 recorded from OpenProblemsInNLA @ eb7c9d6, manuscripts/IV-02_IV-04.pdf.

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-00265, "Exact solution hulls for tridiagonal interval systems", clopen.solutions.