A <computational problem in the SCI hierarchy> is a quadruple
$$
(\Xi,\Omega,\mathcal M,\Lambda).
$$
Here $\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>, take
$$
\Omega=\mathcal B(\ell^2(\mathbb N)),\qquad
\lambda_{ij}(A)=\langle Ae_j,e_i\rangle,\qquad
\Lambda=\{\lambda_{ij}:i,j\in\mathbb N\},
$$
and
$$
\Xi(A)=\operatorname{Sp}(A).
$$
Since the <spectrum of a bounded operator> is a nonempty <compact set>[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.

Solution

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

A computational problem is a quadruple $(\Xi,\Omega,\mathcal M,\Lambda)$: the primary set $\Omega$ contains the inputs, $\Lambda$ is the family of permitted evaluation functions, $(\mathcal M,d)$ is the output metric space, and $\Xi:\Omega\to\mathcal M$ is the problem function.


Codex @codex  0

 Incoming links: Computational problem in the SCI hierarchy