Foundational Analysis Of The Solvability Complexity Index: The Weihrauch-SCI Intermediate Hierarchy

Abstract

The Solvability Complexity Index (SCI) provides an extensional limit-height formalism for recovering a target map $\hat{I}ž$ from finite samples of an evaluation interface $\hat{I}›\subseteq {\mathbb{C}}^{\hat{I}}\text{c◯}$ by finite-height towers of pointwise limits. We first give a foundational analysis of what this extensional framework does and does not determine. We show that the SCI separation axiom is equivalent to a factorization of $\hat{I}ž$ through the full evaluation table, and we isolate the minimal logical role of $\hat{I}›$ as an information interface. To connect the SCI to Type-2 computability and Weihrauch reducibility, we give an effective enrichment for countable $\hat{I}›$ by viewing the evaluation table image $I_{\hat{I}}›\subseteq {\mathbb{C}}^{\mathbb{N}}$ as a represented space and factoring $\hat{I}ž$ as $\hat{\hat{I}}ž$. We then define the Weihrauch-SCI rank of a problem as the least number of iterated limit-oracles needed to compute it in the Weihrauch sense, i.e. the least $k$ such that $\hat{\hat{I}}ž{\le }_W{\lim }^{(k)}$, and prove well-posedness and representation invariance of this rank. A central negative result is that the unrestricted raw type-G SCI model (arbitrary post-processing of finite oracle transcripts) is generally not a computability model in the Type-2/Weihrauch sense: finite-query factorizations collapse raw type-G height, and analytic non-Borel decision problems yield examples with raw ${\mathrm{SCI}}_G=0$ but infinite Weihrauch-SCI rank. We therefore distinguish the raw extensional SCI from implemented SCI variants, where the indexed approximation table is required to be realized uniformly by a chosen class of operations. To recover a robust bridge, we introduce an intermediate SCI hierarchy by restricting the admissible deepest-level post-processing to regularity classes (continuous/Borel/Baire).

Important: [arXiv:2603.18955v2]: additional discussions about evaluation-induced topologies, Kihara-style piecewise-continuity reducibilities, and feasible real RAM models and their connection to the SCI [arXiv:2603.18955v3]: Short+focused version on main results