Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 358 / 1 / a / Solution

A computational problem in the SCI hierarchy is a quadrupleHere $\Omega$ is the primary set of inputs, $\Lambda$ is the set of permitted evaluation functions, $(\mathcal{M},d)$ is the output metric space, and $\Xi :\Omega \to \mathcal{M}$ is the problem function. The Solvability complexity index is defined from the minimum height of a tower of algorithms that computes $\Xi$ from finite subsets of $\Lambda$.

For the classical computational spectral problem, takeandSince the spectrum of a bounded operator is a nonempty compact subset of the complex numbers, one may take $\mathcal{M}$ to be the nonempty compact subsets of $\mathbb{C}$ with the Hausdorff distance. The Attouch--Wets topology gives an equivalent convenient formulation on bounded spectral sets and also extends naturally to unbounded closed sets. This choice of $\mathcal{M}$ makes convergence mean convergence of the whole spectrum as a set, including both the absence of persistent spectral pollution and the approximation of every genuine spectral point.