Solvability complexity index (SCI)

The solvability complexity index counts nested limiting processes needed to compute a mathematical object from prescribed finite information. Arithmetic towers use finite arithmetic operations and comparisons at each stage.

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.

A general algorithm reads only finitely many evaluations for each input, its output depends only on their values, and another input giving those same values causes it to request the same finite information. No restriction is placed on the finite computation performed after reading the data.

An arithmetic algorithm is a general algorithm in the SCI hierarchy whose finite computation uses only finitely many arithmetic operations and comparisons on the evaluated data.

In the ${\Delta }_1$ inexact-information model, a requested evaluation $\lambda (A)$ at precision $m$ may be replaced by any value within $2^{-m}$ of the exact value. An algorithm must work for every admissible stream of such approximations.

For a map $F:X\to X$, a perfect measurement device may query any $x\in X$ and any precision $m$, receiving $y$ with $d(F(x),y)\le 2^{-m}$. It is perfect in the information-theoretic sense: there is no sampling restriction and measurement error can be made arbitrarily small, although every terminating algorithm makes only finitely many queries.

A tower of algorithms of height $k$ is a family ${\Gamma }_{n_k,\dots ,n_1}$ of finite-information algorithms such thatfor every input $A$. The Solvability complexity index is the least possible height.

The classical computational spectral problem takes $\Omega =\mathcal{B}({\ell }^2(\mathbb{N}))$, reads the matrix entries $⟨A{e}_j,e_i⟩$, and asks for $\mathrm{Sp}(A)$ in the Hausdorff distance or Attouch--Wets topology. Its Solvability complexity index is three for general bounded operators.

For a bi-infinite zero-one matrix, ask whether one uniform bound $D$ exists such that each column either contains fewer than $D$ ones or contains infinitely many ones in both directions. This decision problem has Solvability complexity index three even for general algorithms and is a standard source of lower bounds by reduction.

Verification means that a finite-stage output comes with a mathematically valid one-sided or two-sided error guarantee. Convergence in one limit alone does not provide such a certificate at any specified finite stage.