Enclosing solutions of linear interval equations is NP-hard (Q1340883)

Assume that not any problem solvable by a nondeterministic polynomial- time algorithm can also be solved by a polynomial-time algorithm. Then it is shown that there does not exist a polynomial-time algorithm which for each \(n\times n\) interval matrix \(A^ I\) and each interval vector \(b^ I\) with \(n\) components would --- yield an enclosure of the solution set \(X(A^ I,b^ I):= \{x\mid Ax= b\) for some \(A\in A^ I\), \(b\in b^ I\}\) provided \(X(A^ I,b^ I)\) is bounded, --- issue an error message if \(X(A^ I,b^ I)\) is unbounded.