2026

Foundational Analysis Of The Solvability Complexity Index: The Weihrauch-SCI Intermediate Hierarchy And A Koopman Operator Example
Foundational Analysis Of The Solvability Complexity Index: The Weihrauch-SCI Intermediate Hierarchy And A Koopman Operator Example

Christopher Sorg

ArXiv 2026-03-19

The Solvability Complexity Index (SCI) provides an abstract notion of computing a target map $\Xi$ from finitely many oracle evaluations $\Lambda\subseteq \mathbb{C}$ via 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 \enquote{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 type-$G$ SCI model (arbitrary post-processing of finite oracle transcripts) is generally not comparable to Weihrauch/Type-2 complexity: finite-query factorizations collapse type-$G$ height, and analytic (non-Borel) decision problems yield examples with $\mathrm{SCI}_{G}=0$ but infinite Weihrauch-SCI rank. 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 genuine hierarchies, and we establish comparison theorems showing what each restriction logically enforces (e.g.\ Borel towers compute only Borel targets; continuous-base towers yield finite Baire class). As an application, we reinterpret the SCI classification of Koopman spectral approximation problems as an instance of the intermediate hierarchy.

[arXiv]

Foundational Analysis Of The Solvability Complexity Index: The Weihrauch-SCI Intermediate Hierarchy And A Koopman Operator Example

Christopher Sorg

ArXiv 2026-03-19

The Solvability Complexity Index (SCI) provides an abstract notion of computing a target map $\Xi$ from finitely many oracle evaluations $\Lambda\subseteq \mathbb{C}$ via 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 \enquote{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 type-$G$ SCI model (arbitrary post-processing of finite oracle transcripts) is generally not comparable to Weihrauch/Type-2 complexity: finite-query factorizations collapse type-$G$ height, and analytic (non-Borel) decision problems yield examples with $\mathrm{SCI}_{G}=0$ but infinite Weihrauch-SCI rank. 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 genuine hierarchies, and we establish comparison theorems showing what each restriction logically enforces (e.g.\ Borel towers compute only Borel targets; continuous-base towers yield finite Baire class). As an application, we reinterpret the SCI classification of Koopman spectral approximation problems as an instance of the intermediate hierarchy.

[arXiv]

Computability of the Hahn-Banach Theorem Revisited
Computability of the Hahn-Banach Theorem Revisited

Vasco Brattka, Christopher Sorg

ArXiv 2026-03-17

Computational properties of the Hahn-Banach theorem have been studied in computable, constructive and reverse mathematics and in all these approaches the theorem is equivalent to weak König's lemma. Gherardi and Marcone proved that this is also true in the uniform sense of Weihrauch complexity. However, their result requires the underlying space to be variable. We prove that the Hahn-Banach theorem attains its full complexity already for the Banach space $\ell^1$. We also prove that the one-step Hahn-Banach theorem for this space is Weihrauch equivalent to the intermediate value theorem. This also yields a new and very simple proof of the reduction of the Hahn-Banach theorem to weak König's lemma using infinite products. Finally, we show that the Hahn-Banach theorem for $\ell^1$ in the two-dimensional case is Weihrauch equivalent to the lesser limited principle of omniscience.

[arXiv]

Computability of the Hahn-Banach Theorem Revisited

Vasco Brattka, Christopher Sorg

ArXiv 2026-03-17

Computational properties of the Hahn-Banach theorem have been studied in computable, constructive and reverse mathematics and in all these approaches the theorem is equivalent to weak König's lemma. Gherardi and Marcone proved that this is also true in the uniform sense of Weihrauch complexity. However, their result requires the underlying space to be variable. We prove that the Hahn-Banach theorem attains its full complexity already for the Banach space $\ell^1$. We also prove that the one-step Hahn-Banach theorem for this space is Weihrauch equivalent to the intermediate value theorem. This also yields a new and very simple proof of the reduction of the Hahn-Banach theorem to weak König's lemma using infinite products. Finally, we show that the Hahn-Banach theorem for $\ell^1$ in the two-dimensional case is Weihrauch equivalent to the lesser limited principle of omniscience.

[arXiv]

Partial Perception, Knowledge, And Provable Insufficiency
Partial Perception, Knowledge, And Provable Insufficiency

Christopher Sorg

PhilArchive 2026-03-10

This note gives a fully explicit formalization of the question: \textit{When does partial perception yield knowledge, and when is it provably insufficient?} We work in standard epistemic modal logic with truthful public announcements. The carrier set of worlds $W$ is taken as the formal surrogate of the Wittgensteinian logical space; its existence is therefore a semantic premise, not a theorem proved below. The main result is exact: for a factual formula $\alpha$, a truthful observation of type $i$ yields knowledge of $\alpha$ at world $w$ iff the posterior information set $R_a(w) \cap \Pi_{i}(w)$ is included in the set of worlds at which $\alpha$ is true. A complete criterion is then proved for the stronger question whether \textit{any finite sequence} of available perceptions can ever settle whether $\alpha$ is true.

[arXiv]

Partial Perception, Knowledge, And Provable Insufficiency

Christopher Sorg

PhilArchive 2026-03-10

This note gives a fully explicit formalization of the question: \textit{When does partial perception yield knowledge, and when is it provably insufficient?} We work in standard epistemic modal logic with truthful public announcements. The carrier set of worlds $W$ is taken as the formal surrogate of the Wittgensteinian logical space; its existence is therefore a semantic premise, not a theorem proved below. The main result is exact: for a factual formula $\alpha$, a truthful observation of type $i$ yields knowledge of $\alpha$ at world $w$ iff the posterior information set $R_a(w) \cap \Pi_{i}(w)$ is included in the set of worlds at which $\alpha$ is true. A complete criterion is then proved for the stronger question whether \textit{any finite sequence} of available perceptions can ever settle whether $\alpha$ is true.

[arXiv]

Koopman Spectral Computation Beyond The Reflexive Regime: Endpoint Solvability Complexity Index And Type-2 Links
Koopman Spectral Computation Beyond The Reflexive Regime: Endpoint Solvability Complexity Index And Type-2 Links

Christopher Sorg

ArXiv 2026-01-17

We study the Solvability Complexity Index (SCI) of Koopman operator spectral computation in the information-based framework of towers of algorithms. Given a compact metric space $(\mathcal{X},d)$ with a finite Borel measure $\omega$ on $\mathcal{X}$ and a continuous nonsingular map $F:\mathcal{X}\to \mathcal{X}$, our focus is the Koopman operator $\mathcal{K}_F$ acting on $L^p(\mathcal{X},\omega)$ for $p\in\{1,\infty\}$ for the computational problem \[ \Xi_{\sigma_{\mathrm{ap}}}(F) :=\sigma_{\mathrm{ap}}\!\bigl(\mathcal{K}_F\bigr), \] with input access given by point evaluations of $F\mapsto F(x)$ (and fixed quadrature access to $\omega$). We clarify how the $L^1$ case can be brought into the same oracle model as the reflexive regime $1<p<\infty$ by proving a uniform finite-dimensional quadrature compatibility, while highlighting the fundamentally different role played by non-separability at $p=\infty$. Beyond Koopman operators, we also construct a prototype family of decision problems $(\Xi_m)_{m\in\mathbb N}$ realizing prescribed finite tower heights, providing a reusable reduction source for future SCI lower bounds. Finally, we place these results deeper in the broader computational landscape of Type-2/Weihrauch theory.

[arXiv]

Koopman Spectral Computation Beyond The Reflexive Regime: Endpoint Solvability Complexity Index And Type-2 Links

Christopher Sorg

ArXiv 2026-01-17

We study the Solvability Complexity Index (SCI) of Koopman operator spectral computation in the information-based framework of towers of algorithms. Given a compact metric space $(\mathcal{X},d)$ with a finite Borel measure $\omega$ on $\mathcal{X}$ and a continuous nonsingular map $F:\mathcal{X}\to \mathcal{X}$, our focus is the Koopman operator $\mathcal{K}_F$ acting on $L^p(\mathcal{X},\omega)$ for $p\in\{1,\infty\}$ for the computational problem \[ \Xi_{\sigma_{\mathrm{ap}}}(F) :=\sigma_{\mathrm{ap}}\!\bigl(\mathcal{K}_F\bigr), \] with input access given by point evaluations of $F\mapsto F(x)$ (and fixed quadrature access to $\omega$). We clarify how the $L^1$ case can be brought into the same oracle model as the reflexive regime $1<p<\infty$ by proving a uniform finite-dimensional quadrature compatibility, while highlighting the fundamentally different role played by non-separability at $p=\infty$. Beyond Koopman operators, we also construct a prototype family of decision problems $(\Xi_m)_{m\in\mathbb N}$ realizing prescribed finite tower heights, providing a reusable reduction source for future SCI lower bounds. Finally, we place these results deeper in the broader computational landscape of Type-2/Weihrauch theory.

[arXiv]

2025

Solvability Complexity Index Classification For Koopman Operator Spectra In $L^p$ For $1 < p < \infty$
Solvability Complexity Index Classification For Koopman Operator Spectra In $L^p$ For $1 < p < \infty$

Christopher Sorg

ArXiv 2025-09-19

We study the computation of the approximate point spectrum and the approximate point $\varepsilon$-pseudospectrum of bounded Koopman operators acting on $L^p(\mathcal{X},\omega)$ for $1 < p < \infty$ and a compact metric space $(\mathcal{X}, d_{\mathcal{X}})$ with finite Borel measure $\omega$. Building on finite sections in a computable unconditional Schauder basis of $L^p(\mathcal{X},\omega)$, we design residual tests that use only finitely many evaluations of the underlying map and produce compact sets on a planar grid, that converge in the Hausdorff metric to the target spectral sets, without spectral pollution. From these constructions we obtain a complete classification, in the sense of the Solvability Complexity Index, of how many limiting procedures are inherently necessary.

[arXiv]

Solvability Complexity Index Classification For Koopman Operator Spectra In $L^p$ For $1 < p < \infty$

Christopher Sorg

ArXiv 2025-09-19

We study the computation of the approximate point spectrum and the approximate point $\varepsilon$-pseudospectrum of bounded Koopman operators acting on $L^p(\mathcal{X},\omega)$ for $1 < p < \infty$ and a compact metric space $(\mathcal{X}, d_{\mathcal{X}})$ with finite Borel measure $\omega$. Building on finite sections in a computable unconditional Schauder basis of $L^p(\mathcal{X},\omega)$, we design residual tests that use only finitely many evaluations of the underlying map and produce compact sets on a planar grid, that converge in the Hausdorff metric to the target spectral sets, without spectral pollution. From these constructions we obtain a complete classification, in the sense of the Solvability Complexity Index, of how many limiting procedures are inherently necessary.

[arXiv]