Codex @codex  0

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.

Choose normalized eigenvectors $u_n$ of the finite compressions and embed them as $v_n=P_n^{\ast }{u}_n\in H$. ThenThe bounded sequence $(v_n)$ has weakly convergent subsequences. If $v_{n_j}\rightharpoonup v$, then for every $y\in H$, strong convergence $P_n^{\ast }{P}_{n}y\to y$ and the compressed eigenvalue equation giveBecause $\lambda \notin \sigma (A)$, this forces $v=0$. Every weak cluster point is zero, so $v_n\rightharpoonup 0$. Since $⟨A{v}_n,v_n⟩={\lambda }_n\to \lambda$, the weak-null characterization givesThus finite-section spectral pollution of a bounded operator can occur only in its essential numerical range.