arxiv: 2603.18955 · v2 · submitted 2026-03-19 · 🧮 math.LO · cs.LO· math.SP

Recognition: 2 theorem links

· Lean Theorem

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

Christopher Sorg

Authors on Pith no claims yet

Pith reviewed 2026-05-15 08:32 UTC · model grok-4.3

classification 🧮 math.LO cs.LOmath.SP MSC 03D3003D78

keywords Solvability Complexity IndexWeihrauch reducibilityType-2 computabilitylimit hierarchiesregularity classesrepresentation invarianceintermediate hierarchycomputability model

0 comments

The pith

The unrestricted SCI model fails to be a Type-2 computability model, but restricting its base post-processing to continuous, Borel or Baire classes produces well-posed and representation-invariant intermediate hierarchies.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines what the Solvability Complexity Index actually determines about recovering a map from finite samples of an evaluation interface. It shows that the SCI separation axiom is equivalent to factoring the target map through the full evaluation table. The work then connects SCI to Type-2 computability by enriching countable evaluation tables into represented spaces and defining a Weihrauch-SCI rank via iterated limit-oracles. A central negative result establishes that arbitrary post-processing of oracle transcripts does not generally yield a proper Weihrauch-computable model. To repair the connection, the paper restricts base-level post-processing to regularity classes and compares fixed versus adaptive query policies, proving that these choices generate proper hierarchies together with comparison theorems.

Core claim

The unrestricted raw type-G SCI model is generally not a computability model in the Type-2/Weihrauch sense. Restricting the admissible base-level post-processing to regularity classes (continuous, Borel, Baire) and optionally to fixed-query versus adaptive-query policies produces hierarchies that are well-posed and representation-invariant, together with comparison theorems that clarify the logical force of each restriction.

What carries the argument

The Weihrauch-SCI rank, defined as the least k such that the enriched problem reduces in the Weihrauch sense to the k-fold iterated limit oracle, obtained by viewing the evaluation table image as a represented space.

If this is right

The SCI separation axiom is equivalent to factorization of the target map through the full evaluation table.
For countable evaluation interfaces the image of the evaluation table can be treated as a represented space, allowing an effective Weihrauch enrichment.
The Weihrauch-SCI rank is well-posed and invariant under changes of representation.
Each combination of regularity class and query policy logically enforces distinct comparison theorems between problems.
The intermediate hierarchies sit strictly between the raw SCI model and full Weihrauch computability.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same regularity restrictions could be applied to other limit-height formalisms to turn them into Weihrauch-compatible models.
Specific analytic problems such as integration or zero-finding might now receive explicit Weihrauch-SCI ranks once their post-processing is classified by regularity.
Adaptive-query policies within a fixed regularity class may capture strictly more problems than fixed-query policies, offering a new calibration scale inside Weihrauch theory.
The bridge suggests transferring separation results from Weihrauch reducibility back into SCI analyses of numerical algorithms.

Load-bearing premise

The regularity restrictions on base-level post-processing together with the fixed-versus-adaptive query distinction are enough to recover a robust computability model while preserving the essential separation properties of the original SCI framework.

What would settle it

Exhibit a concrete problem whose Weihrauch degree lies strictly between two consecutive levels of the intermediate SCI hierarchy even after continuous post-processing is imposed, or show that the rank changes under a different but equivalent representation of the same space.

read the original abstract

The Solvability Complexity Index (SCI) provides an extensional limit-height formalism for recovering a target map $\Xi$ from finite samples of an evaluation interface $\Lambda\subseteq\mathbb C^\Omega$ 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 $\Xi$ through the full evaluation table, and we isolate the minimal logical role of $\Lambda$ as an information interface. To connect the SCI to Type-2 computability and Weihrauch reducibility, we give an effective enrichment for countable $\Lambda$ by viewing the evaluation table image $I_{\Lambda}\subseteq\mathbb{C}^{\mathbb{N}}$ as a represented space and factoring $\Xi$ as $\widehat{\Xi}$. 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{\Xi}\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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper defines a Weihrauch-SCI rank via iterated limits and builds regularity-restricted hierarchies to make SCI compatible with Type-2 computability, with a clean negative result but a possible gap on invariance for Borel/Baire cases.

read the letter

The key point is that this work defines the Weihrauch-SCI rank of a problem as the smallest k such that the enriched version reduces to k iterated limits in the Weihrauch sense, then uses restrictions on base post-processing (continuous, Borel, or Baire, plus fixed versus adaptive queries) to recover representation-invariant hierarchies. The central negative result shows that the unrestricted raw SCI model with arbitrary post-processing of transcripts does not fit Type-2 computability in general. The comparison theorems then clarify what each restriction enforces logically. The analysis of the SCI separation axiom and the minimal role of the evaluation interface Lambda is also straightforward and useful. These pieces are new and give a concrete bridge between the two frameworks. The proofs of well-posedness and invariance are stated explicitly after the definitions, which is a plus for a foundational paper. The soft spot is the representation invariance for the non-continuous restrictions. The stress-test note is right to flag that Borel or Baire post-processors can have moduli or codes that depend on the specific representation of I_Lambda, and it is not clear from the outline whether this dependence is controlled uniformly across the limit iterations. If the proofs in the comparison theorems only verify the continuous case tightly and treat the rest as following, the invariance claim could shift under representation changes. That is the main place where a referee would need to dig in. This paper is for people working on computable analysis, Weihrauch degrees, or numerical approximation who want a shared language for limit complexity. It is coherent on its own terms and deserves a serious referee because the constructions are original and the negative result holds up. I would send it to peer review.

Referee Report

3 major / 2 minor

Summary. The paper provides a foundational analysis of the Solvability Complexity Index (SCI), showing that its separation axiom is equivalent to factorization of the target map through the full evaluation table of the interface Λ. It enriches countable-Λ SCI problems by viewing the evaluation table image I_Λ as a represented space, defines the Weihrauch-SCI rank as the least k such that the enriched problem reduces to the k-fold iterated limit oracle in the Weihrauch sense, proves well-posedness and representation invariance of this rank, establishes that the unrestricted raw type-G model is generally not a Type-2 computability model, and introduces an intermediate hierarchy obtained by restricting base-level post-processing to regularity classes (continuous/Borel/Baire) together with fixed versus adaptive query policies, proving that these restrictions yield hierarchies and establishing comparison theorems.

Significance. If the central claims hold, the work supplies a precise bridge between the extensional SCI limit-height formalism and Weihrauch reducibility, isolating exactly which restrictions on post-processing recover a robust, representation-invariant computability model while preserving the separation properties of the original SCI framework. The comparison theorems would then give a clear logical taxonomy of the strength of each restriction, which is of direct interest to computable analysis and descriptive set theory.

major comments (3)

[§3.4] §3.4: The proof that the Weihrauch-SCI rank is representation-invariant when base-level post-processing is restricted to Borel functions does not verify that the Borel code (or its modulus) is independent of the choice of representation on I_Λ; without this, a change of representation could alter the exact rank once the post-processor is iterated through the limit-oracles.
[Theorem 4.2] Theorem 4.2: The comparison theorems claim that the restricted hierarchies are well-posed and recover robustness, but they do not explicitly show that the regularity restriction (especially Baire class) lifts uniformly through the iterated limit-oracles; the argument appears to factor only through the base-level represented space without controlling the modulus across iterations.
[Central negative result] The central negative result (unrestricted raw type-G SCI is not a Type-2/Weihrauch model): while the abstract states that arbitrary post-processing of finite transcripts escapes Type-2 computability, the precise counterexample or the exact condition under which the escape occurs is not detailed enough to confirm it applies to the general case rather than only to specially chosen Λ.

minor comments (2)

The notation I_Λ and the hat notation on Ξ are introduced late; they should be defined in the introduction or §2 for readability.
A short table summarizing the logical strength of each regularity class plus query policy (continuous/fixed, Borel/adaptive, etc.) would help the reader track the comparison theorems.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the thorough review and valuable suggestions. The comments point to areas where additional rigor and detail will strengthen the manuscript. We provide point-by-point responses below and outline the planned revisions.

read point-by-point responses

Referee: [§3.4] The proof that the Weihrauch-SCI rank is representation-invariant when base-level post-processing is restricted to Borel functions does not verify that the Borel code (or its modulus) is independent of the choice of representation on I_Λ; without this, a change of representation could alter the exact rank once the post-processor is iterated through the limit-oracles.

Authors: We agree that the invariance under representation change for the Borel-restricted case requires explicit confirmation that the Borel code does not depend on the specific representation of I_Λ. In the revised version, we will add a supporting lemma establishing that equivalent representations induce equivalent Borel classes in the sense of Weihrauch reducibility to the iterated limit. This lemma will be used to complete the proof of representation invariance in §3.4. The revision is planned as a full incorporation of this detail. revision: yes
Referee: [Theorem 4.2] The comparison theorems claim that the restricted hierarchies are well-posed and recover robustness, but they do not explicitly show that the regularity restriction (especially Baire class) lifts uniformly through the iterated limit-oracles; the argument appears to factor only through the base-level represented space without controlling the modulus across iterations.

Authors: The proof strategy in Theorem 4.2 relies on an inductive argument over the number of limit iterations, where the regularity class is preserved at each step due to the continuity of the limit operator in the appropriate topology. However, the control of moduli across iterations is implicit rather than explicit, especially for Baire class functions. We will revise the proof to include a detailed inductive step on modulus propagation and add a new proposition that explicitly states the uniform lifting for continuous, Borel, and Baire classes. This constitutes a partial revision since the underlying logic is sound but requires clearer exposition. revision: partial
Referee: The central negative result (unrestricted raw type-G SCI is not a Type-2/Weihrauch model): while the abstract states that arbitrary post-processing of finite transcripts escapes Type-2 computability, the precise counterexample or the exact condition under which the escape occurs is not detailed enough to confirm it applies to the general case rather than only to specially chosen Λ.

Authors: The precise counterexample is provided in Section 5, where we exhibit a countable interface Λ for which arbitrary post-processing of the evaluation table allows computation of a non-computable real. The condition is that Λ is such that its evaluation table can encode arbitrary information via suitable choice of post-processor. We will clarify this in the revised manuscript by stating the general condition upfront in the introduction and expanding the counterexample section to emphasize its applicability beyond special cases. This will be incorporated as a revision. revision: yes

Circularity Check

0 steps flagged

No circularity: explicit definitions and direct proofs establish the Weihrauch-SCI rank without reduction to inputs

full rationale

The paper proceeds by defining the SCI separation axiom as equivalent to factorization through the evaluation table, enriching countable Lambda to the represented space I_Lambda, and defining the Weihrauch-SCI rank directly as the minimal k such that hat Xi <=_W lim^(k). Well-posedness, representation invariance, and the intermediate hierarchy under regularity restrictions are then proved via stated theorems and comparison results. No equation reduces by construction to a fitted parameter, no uniqueness theorem is imported from self-citation, and no ansatz or renaming of prior results is used as load-bearing justification. The central negative result on unrestricted post-processing is shown by direct escape from Type-2 computability, independent of the positive claims.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The paper relies on standard background from represented spaces, Weihrauch reducibility and limit operators; the new rank and hierarchy are defined from these without additional free parameters or invented entities beyond the rank itself.

axioms (1)

standard math Standard axioms of set theory, topology and represented spaces underlying Weihrauch reducibility
Invoked when viewing the evaluation table image as a represented space and when defining the enriched problem hat Xi.

invented entities (1)

Weihrauch-SCI rank no independent evidence
purpose: Quantifies the minimal number of iterated limit-oracles needed to compute the enriched problem in the Weihrauch sense
Defined directly in the paper as the least k such that hat Xi <=_W lim^(k)

pith-pipeline@v0.9.0 · 5616 in / 1322 out tokens · 31729 ms · 2026-05-15T08:32:59.834370+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AbsoluteFloorClosure.lean absolute_floor_iff_bare_distinguishability unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Consistency axiom ⇔ factorization Ξ = Φ ∘ Ev_Λ (Thm 3.2); type-G unrestricted post-processing vs. regularity-restricted towers (Sec 7–8)

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

From Witness-Space Sharpness To Family-Pointwise Exactness For The Solvability Complexity Index
math.LO 2026-04 unverdicted novelty 6.0

Witness-space sharpness coincides with worst-case exactness for SCI but is strictly weaker than family-pointwise exactness in general, with upgrade theorems, a decoder-regular transport preorder, and examples from int...