2026
Finite-Query Collapse and Modal Exact Bases in the SCI Hierarchy
ArXiv 2026-06-11
We study the exact-basis problem for Solvability Complexity Index (SCI) computational problem families through finite-query transports. A raw finite-query reduction permits arbitrary encodings and finite transcript reconstructions, with only a continuous output decoder. For the Colbrook-Hansen (CH23) singleton-window spectral/pseudospectral block, this raw preorder collapses the expected two-source structure: the diagonal exact spectral and fixed- pseudospectral sources are raw- and continuous-finite-query equivalent, and, for computable under the evaluation-name representations, TTE-finite-query equivalent, so the six-problem ambient is raw-principal. We then introduce modal finite-query preorders, whose admissibility conditions may restrict encodings, decoders, reconstructions, uniformity, and geometric naturality. We also characterize TTE finite-query transport as computable point transport with a uniform finite interface trace; after forgetting the trace this gives strong Weihrauch reducibility, and the implication is strict. Under a CH23 geometric modality generated by representation inclusions, unitary and graph relabelings, and neutral stabilizations, the same ambient has exactly two minimal exact sources. This gives a calibrated reformulation of the exact-basis problem: natural SCI families should be classified by modality-indexed exact bases and refinement maps, not by one raw preorder alone.
From Witness-Space Sharpness To Family-Pointwise Exactness For The Solvability Complexity Index
ArXiv 2026-04-14
We study how exact Solvability Complexity Index (SCI) statements should be formulated for families of computational problems rather than for single problems. While the equality $\mathrm{SCI}_G (\mathcal P)=k$ is unambiguous for an individual computational problem $\mathcal P$, the family setting requires one to distinguish family-pointwise exactness, witness-space sharpness, and worst-case exactness. We formalize this trichotomy, prove that witness-space sharpness coincides with worst-case exactness but is, in general, strictly weaker than family-pointwise exactness, and give a canonical source-family example witnessing the strictness. We then establish two positive upgrade theorems: an abstract pullback principle and a concrete finite-query criterion guaranteeing that witness-space sharpness upgrades to family-pointwise exactness. Next, we introduce a decoder-regular finite-query transport preorder on SCI computational problems, prove that it is a preorder, derive a transport-saturation sufficient criterion extending the principal-source package, and show that the associated transport degrees need not form a lattice in full generality. We analyze the natural decoder classes $\mathscr R_{\mathrm{cont}}$ and $\mathscr R_{\mathrm{Bor}}$: on the full class the corresponding quotients are not upper semilattices, while on the nondegenerate subclass the preorder is upward and downward directed. Finally, we exhibit two natural positive families realizing the principal transport mechanism: exact integration on compact intervals and a fixed-window spectral decision family obtained by block-diagonal stabilization.
Foundational Analysis Of The Solvability Complexity Index: The Weihrauch-SCI Intermediate Hierarchy
ArXiv 2026-03-19
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: 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) 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. Finally, we give self-contained canonical source problems over Cantor-matrix inputs which realize arbitrary finite standard raw type-G SCI heights. These examples are not presented as computability models by themselves; rather, they are calibration objects for the extensional SCI and for the interaction between finite-query information, Borel hierarchy level, restricted SCI towers, and Weihrauch-style uniform iterated-limit complexity.
Computability of the Hahn-Banach Theorem Revisited
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.
Partial Perception, Knowledge, And Provable Insufficiency
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.
Endpoint Koopman Spectral Computation: $L^1$ Residual Bounds, $L^{\infty}$ Instability, and Point-Spectral SCI Calibration Families
ArXiv 2026-01-17
We study endpoint Koopman spectral computation from the viewpoint of the Solvability Complexity Index (SCI). Let $(\mathcal X,d)$ be a compact metric space with finite Borel measure $\omega$, and let $\mathcal K_F$ be the Koopman operator associated with a continuous nonsingular map $F:\mathcal X \to \mathcal X$. First, on $L^1(\mathcal X,\omega)$, we record the endpoint residual upper-bound in the target-split form. The regularized compact fixed-$\varepsilon$ target $R_{\mathrm{ap},\varepsilon}(\mathcal K_F)$ is separated from the closed fixed-\(\varepsilon\) target $C_{\mathrm{ap},\varepsilon}(\mathcal K_F)$ and from the exact approximate point spectrum $\sigma_{\mathrm{ap}}(\mathcal K_F)$. This endpoint statement uses the same point-evaluation plus fixed-quadrature information model as the $1<p<\infty$ residual theory. Second, we isolate two obstructions at the nonseparable endpoint $L^\infty$. Fixed quadrature schemes do not discretize the full $L^{\infty}$ unit sphere, and even inside measure-preserving Cantor homeomorphisms the map $F\mapsto \sigma_{\mathrm{ap}}(\mathcal K_F : L^{\infty} \to L^{\infty})$ is maximally discontinuous in Hausdorff distance under arbitrarily small uniform perturbations of $F$. We also show that finite-period Silver-tree block constructions cannot yield analytic hardness for the $L^{\infty}$ approximate point spectrum: for a fixed non-torsion $z_0\in\mathbb T$, the condition $z_0\in\sigma_{\mathrm{ap}}(\mathcal K_{F}:L^{\infty} \to L^{\infty})$ collapses to a Borel unbounded-period condition. In addition, fixed $L^{\infty}$ point-eigenvalue membership is Borel in the measure-preserving continuous class, so one fixed eigenvalue cannot encode a non-Borel tree predicate. Third, we construct Koopman point-spectrum calibration families on the Cantor space. For each $m\in \mathbb{N}$, we build a family of continuous measure-preserving Cantor homeomorphisms whose labelled exact $L^{\infty}$ point-eigenvalue decisions are finite-query equivalent to the canonical alternating Cantor-matrix source problem of raw type-$G$ height $m$. Consequently these Koopman decision problems have exact raw type-$G$ SCI height $m$, and their tagged disjoint union has raw type-$G$ SCI $\infty$.
2025
Residual SCI Upper Bounds And Lower Witnesses For Koopman Approximate Point Spectra In $L^p$ For $1<p<\infty$
ArXiv 2025-09-19
We study residual computation of approximate point spectral sets of bounded Koopman operators $\mathcal K_F$ on $L^p(\mathcal X,\omega)$, $1<p<\infty$, where $\mathcal X$ is a compact metric space and $\omega$ is a finite Borel measure. The input is the underlying map $F : \mathcal X \to \mathcal X$, accessed through point evaluations, and the output metric is the Hausdorff metric on non-empty compact subsets of $\mathbb C$. For a bounded operator $T$, we distinguish the regularized approximate point $\varepsilon$-pseudospectrum $R_{\mathrm{ap},\varepsilon}(T)$ from the closed approximate point $\varepsilon$-pseudospectrum $C_{\mathrm{ap},\varepsilon}(T)$. The latter is the direct closed lower-norm analogue of the approximate point $\varepsilon$-pseudospectrum used in the $L^2$ Koopman SCI theory. Using continuous finite-dimensional dictionaries and tagged quadrature residuals, we prove SCI upper bounds for $R_{\mathrm{ap},\varepsilon}(T)$, $C_{\mathrm{ap},\varepsilon}(T)$, and $\sigma_{\mathrm{ap}}$ on four natural classes of maps: continuous nonsingular maps, maps with a prescribed modulus of continuity, measure-preserving maps, and maps satisfying both measure preservation and a prescribed modulus. In the measure-preserving case the two fixed-$\varepsilon$ targets coincide, because the Koopman operator is an $L^p$-isometry. We also prove fixed-$\varepsilon$ sharpness on a known-modulus measure-preserving witness class and a boundary lower obstruction for the closed nonsingular problem. Finally, we identify the remaining no-modulus sharpness problem for the exact approximate point spectrum and explain why the natural locking strategy cannot prove it.