Exact tridiagonal interval determinants and solution hulls are NP-hard

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
tridiagonal interval linear system, are NP-hard. The reduction uses
independent interval entries, fixed superdiagonal entries equal to $1$, and an
interval family all of whose members are nonsingular; for the hull, the
right-hand side is the single point $-e_n$. Exact-output upper bounds in
$\mathsf{FP}^{\mathsf{NP}}$ are also given, covering empty solution sets and
infinite hull endpoints, so a polynomial-time algorithm for either
exact-output problem exists if and only if $\mathsf{P} = \mathsf{NP}$.