pith. sign in

arxiv: 2604.12750 · v2 · pith:C2H6UYBKnew · submitted 2026-04-14 · 🧮 math.LO · cs.CC· math.DS· math.FA

From Witness-Space Sharpness To Family-Pointwise Exactness For The Solvability Complexity Index

Christopher Sorg This is my paper

Pith reviewed 2026-05-19 17:45 UTC · model grok-4.3

classification 🧮 math.LO cs.CCmath.DSmath.FA
keywords solvability complexity indexwitness-space sharpnessfamily-pointwise exactnessworst-case exactnessfinite-query transportpullback principledecoder classescomputational problems
0
0 comments X

The pith

Witness-space sharpness coincides with worst-case exactness but is strictly weaker than family-pointwise exactness for SCI families

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

The paper examines how to state exact solvability complexity index results for families of computational problems rather than isolated ones. It distinguishes family-pointwise exactness, witness-space sharpness, and worst-case exactness, proving that sharpness and worst-case exactness are equivalent yet both fall short of the pointwise version in general. A canonical source-family example is supplied to show the gap. Two upgrade results—an abstract pullback principle and a finite-query criterion—are given to lift sharpness to family-pointwise exactness when suitable decoder and transport conditions hold.

Core claim

Witness-space sharpness coincides with worst-case exactness but is, in general, strictly weaker than family-pointwise exactness; a canonical source-family example witnesses the strictness. An abstract pullback principle and a concrete finite-query criterion guarantee that sharpness upgrades to family-pointwise exactness. A decoder-regular finite-query transport preorder is introduced, shown to be a preorder, and analyzed on the decoder classes R_cont and R_Bor, with natural positive families such as exact integration on compact intervals realizing the transport mechanism.

What carries the argument

The decoder-regular finite-query transport preorder together with the abstract pullback principle for upgrading sharpness properties across problem families

If this is right

  • Witness-space sharpness upgrades to family-pointwise exactness via the abstract pullback principle under decoder regularity conditions.
  • A concrete finite-query criterion supplies a sufficient test for the upgrade in families such as integration and spectral decision.
  • The transport preorder is not an upper semilattice on the full decoder classes but is upward and downward directed on the nondegenerate subclass.
  • Exact integration on compact intervals and fixed-window spectral decision families realize the principal transport mechanism.

Where Pith is reading between the lines

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

  • Researchers studying families in computable analysis could first verify sharpness and then apply the upgrade criteria to reach the stronger pointwise statement.
  • The transport preorder may help locate minimal source problems from which exactness results propagate to larger families.
  • The three-way distinction among exactness notions could be tested in other computational indices beyond SCI.

Load-bearing premise

The families admit decoder-regular finite-query transports and the decoder classes satisfy the regularity conditions needed for the pullback principle to apply.

What would settle it

The canonical source-family example; if it fails to separate witness-space sharpness from family-pointwise exactness, the claim of strict weakness is false.

read the original abstract

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.

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.

Referee Report

1 major / 1 minor

Summary. The paper distinguishes three notions of exact Solvability Complexity Index (SCI) statements for families of computational problems: family-pointwise exactness, witness-space sharpness, and worst-case exactness. It proves that witness-space sharpness coincides with worst-case exactness but is strictly weaker than family-pointwise exactness in general, witnessed by a canonical source-family example. Two upgrade theorems are established—an abstract pullback principle and a concrete finite-query criterion—under the assumption of decoder-regular finite-query transports. The paper introduces a decoder-regular finite-query transport preorder on SCI problems, proves it is a preorder, derives a transport-saturation criterion, shows that transport degrees need not form a lattice, and analyzes the decoder classes R_cont and R_Bor (quotients not upper semilattices on the full class, but the preorder is directed on the nondegenerate subclass). Two concrete families are exhibited: exact integration on compact intervals and fixed-window spectral decision via block-diagonal stabilization, realizing the principal transport mechanism.

Significance. If the results hold, the work clarifies the precise formulation of exact SCI statements in the family setting, which is important for computational analysis and complexity theory. The trichotomy, upgrade theorems, and transport preorder provide systematic tools for strengthening SCI results from sharpness to exactness. Credit is due for the concrete canonical example witnessing strictness, the explicit proof that the transport relation is a preorder, the analysis of the decoder classes, and the exhibition of two natural families realizing the transport mechanism.

major comments (1)
  1. [sections on upgrade theorems and exhibited families] The upgrade theorems (abstract pullback principle and finite-query criterion) are stated to lift witness-space sharpness to family-pointwise exactness only when families admit decoder-regular finite-query transports and decoder classes satisfy the requisite regularity conditions. For the two exhibited families (exact integration on compact intervals; fixed-window spectral decision via block-diagonal stabilization), the manuscript invokes these conditions but does not supply an explicit, independent check that the chosen decoders in R_cont or R_Bor are regular and finite-query in a manner independent of the target SCI exactness statement. This verification is load-bearing for the claim that the upgrades apply to these canonical examples.
minor comments (1)
  1. [introduction of decoder classes] Notation for the decoder classes R_cont and R_Bor is introduced without an early consolidated definition or comparison table, which would aid readability when the classes are later analyzed for semilattice properties.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading, positive assessment of significance, and constructive major comment. We address the point below and will revise the manuscript to incorporate explicit verifications.

read point-by-point responses

  1. Referee: The upgrade theorems (abstract pullback principle and finite-query criterion) are stated to lift witness-space sharpness to family-pointwise exactness only when families admit decoder-regular finite-query transports and decoder classes satisfy the requisite regularity conditions. For the two exhibited families (exact integration on compact intervals; fixed-window spectral decision via block-diagonal stabilization), the manuscript invokes these conditions but does not supply an explicit, independent check that the chosen decoders in R_cont or R_Bor are regular and finite-query in a manner independent of the target SCI exactness statement. This verification is load-bearing for the claim that the upgrades apply to these canonical examples.

    Authors: We thank the referee for this observation. The manuscript defines decoder-regular finite-query transports and states that the decoders selected for the integration family (in R_cont) and the spectral family (in R_Bor) satisfy the requisite conditions, but we agree that an explicit, independent verification—separate from the target exactness claims—would strengthen the exposition and make the applicability of the upgrade theorems fully transparent. In the revised manuscript we will add dedicated verification paragraphs (or short subsections) for each family: these will confirm regularity and finite-query properties by direct appeal to the definitions and the concrete decoder constructions, without presupposing the SCI exactness results. This revision addresses the load-bearing character of the verification. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained from new definitions

full rationale

The paper introduces witness-space sharpness, family-pointwise exactness, worst-case exactness, decoder-regular finite-query transports, and associated preorders as novel formal notions for SCI on families. It proves their relations (coincidence of sharpness and worst-case exactness, strict weakness relative to family-pointwise exactness) and states conditional upgrade theorems (abstract pullback principle, finite-query criterion) directly from these definitions and the regularity assumptions on decoders. Concrete families (exact integration, block-diagonal spectral decision) are exhibited as realizations under the stated conditions rather than as inputs that force the theorems by construction. No quoted step equates a derived result to a fitted parameter, self-citation chain, or renamed input; the central claims retain independent content from the formalization and proofs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper works within standard ZFC set theory and the existing framework of Solvability Complexity Index; it introduces definitional notions such as witness-space sharpness and decoder-regular transport but does not postulate new physical or mathematical entities.

axioms (1)
  • standard math Standard axioms of set theory and first-order logic
    Used throughout to formalize definitions of families, decoders, and preorders.

pith-pipeline@v0.9.0 · 5802 in / 1369 out tokens · 51639 ms · 2026-05-19T17:45:21.701451+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

11 extracted references · 11 canonical work pages · 2 internal anchors

  1. [1]

    Computing spectra--on the solvability complexity index hierarchy and towers of algorithms

    Jonathan Ben-Artzi, Matthew J Colbrook, Anders C Hansen, Olavi Nevanlinna, and Markus Seidel. Computing spectra--on the solvability complexity index hierarchy and towers of algorithms. arXiv preprint arXiv:1508.03280 , 2015

    work page arXiv 2015

  2. [2]

    Colbrook and Anders C

    Matthew J. Colbrook and Anders C. Hansen. The foundations of spectral computations via the solvability complexity index hierarchy. J. Eur. Math. Soc. (JEMS) , 25(12):4639--4718, 2023

    work page 2023

  3. [3]

    Davis and Philip Rabinowitz

    Philip J. Davis and Philip Rabinowitz. Methods of numerical integration . Computer Science and Applied Mathematics. Academic Press, Inc., Orlando, FL, second edition, 1984

    work page 1984

  4. [4]

    On the solvability complexity index, the -pseudospectrum and approximations of spectra of operators

    Anders Hansen. On the solvability complexity index, the -pseudospectrum and approximations of spectra of operators. Journal of the American Mathematical Society , 24(1):81--124, 2011

    work page 2011

  5. [5]

    Perturbation theory for linear operators

    Tosio Kato. Perturbation theory for linear operators . Classics in Mathematics. Springer-Verlag, Berlin, 1995. Reprint of the 1980 edition

    work page 1995

  6. [6]

    Game characterizations and lower cones in the W eihrauch degrees

    Hugo Nobrega and Arno Pauly. Game characterizations and lower cones in the W eihrauch degrees. Log. Methods Comput. Sci. , 15(3):Paper No. 11, 29, 2019

    work page 2019

  7. [7]

    Tractability of multivariate problems

    Erich Novak and Henryk Wo\'zniakowski. Tractability of multivariate problems. V olume II : S tandard information for functionals , volume 12 of EMS Tracts in Mathematics . European Mathematical Society (EMS), Z\"urich, 2010

    work page 2010

  8. [8]

    Principles of mathematical analysis

    Walter Rudin. Principles of mathematical analysis . International Series in Pure and Applied Mathematics. McGraw-Hill Book Co., New York-Auckland-D\"usseldorf, third edition, 1976

    work page 1976

  9. [9]

    Residual SCI Upper Bounds And Lower Witnesses For Koopman Approximate Point Spectra In $L^p$ For $1<p<\infty$: Extended Version

    Christopher Sorg. Solvability complexity index classification for koopman operator spectra in L ^p for 1< p< . arXiv preprint arXiv:2509.16016 , 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  10. [10]

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

    Christopher Sorg. Foundational analysis of the solvability complexity index: The weihrauch-sci intermediate hierarchy and a koopman operator example. arXiv preprint arXiv:2603.18955 , 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  11. [11]

    J. F. Traub, G. W. Wasilkowski, and H. Wo\'zniakowski. Information-based complexity . Computer Science and Scientific Computing. Academic Press, Inc., Boston, MA, 1988. With contributions by A. G. Werschulz and T. Boult

    work page 1988