Foundational Analysis Of The Solvability Complexity Index: The Weihrauch-SCI Intermediate Hierarchy
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918501462048768 |
|---|---|
| author | Sorg, Christopher |
| author_facet | Sorg, Christopher |
| contents | The Solvability Complexity Index (SCI) provides an extensional limit-height formalism for recovering a target map $Ξ$ from finite samples of an evaluation interface $Λ\subseteq\mathbb 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 $Ξ$ through the full evaluation table, and we isolate the minimal logical role of $Λ$ as an information interface.
To connect the SCI to Type-2 computability and Weihrauch reducibility, we give an effective enrichment for countable $Λ$ by viewing the evaluation table image $I_Λ\subseteq\mathbb{C}^{\mathbb{N}}$ as a represented space and factoring $Ξ$ as $\widehatΞ$. 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 $\widehatΞ\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. To recover a robust bridge, we introduce an intermediate SCI hierarchy by restricting the admissible base-level post-processing to regularity classes (continuous/Borel/Baire) and, optionally, to fixed-query versus adaptive-query policies. We prove that these restrictions form hierarchies, and we establish comparison theorems showing what each restriction logically enforces. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_18955 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Foundational Analysis Of The Solvability Complexity Index: The Weihrauch-SCI Intermediate Hierarchy Sorg, Christopher Logic Logic in Computer Science Spectral Theory 03D78, 03D30, 03D55, 03E15, 68Q17, 54C35 The Solvability Complexity Index (SCI) provides an extensional limit-height formalism for recovering a target map $Ξ$ from finite samples of an evaluation interface $Λ\subseteq\mathbb 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 $Ξ$ through the full evaluation table, and we isolate the minimal logical role of $Λ$ as an information interface. To connect the SCI to Type-2 computability and Weihrauch reducibility, we give an effective enrichment for countable $Λ$ by viewing the evaluation table image $I_Λ\subseteq\mathbb{C}^{\mathbb{N}}$ as a represented space and factoring $Ξ$ as $\widehatΞ$. 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 $\widehatΞ\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. To recover a robust bridge, we introduce an intermediate SCI hierarchy by restricting the admissible base-level post-processing to regularity classes (continuous/Borel/Baire) and, optionally, to fixed-query versus adaptive-query policies. We prove that these restrictions form hierarchies, and we establish comparison theorems showing what each restriction logically enforces. |
| title | Foundational Analysis Of The Solvability Complexity Index: The Weihrauch-SCI Intermediate Hierarchy |
| topic | Logic Logic in Computer Science Spectral Theory 03D78, 03D30, 03D55, 03E15, 68Q17, 54C35 |
| url | https://arxiv.org/abs/2603.18955 |