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

Recognition: unknown

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

Christopher Sorg

Authors on Pith no claims yet

Pith reviewed 2026-05-10 13:44 UTC · model grok-4.3

classification 🧮 math.LO cs.CCmath.DSmath.FA

keywords Solvability Complexity Indexwitness-space sharpnessfamily-pointwise exactnessworst-case exactnessKoopman operatorstransport preorderdecoder classescomputational families

0 comments

The pith

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

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

This paper examines how exact statements about the Solvability Complexity Index should be phrased when the objects are families of computational problems rather than single problems. It distinguishes three notions: family-pointwise exactness, which demands the property for every individual problem; witness-space sharpness, which concerns the existence of suitable witnesses in an ambient space; and worst-case exactness, which focuses on the hardest case. The core result formalizes their relationships, proves that witness-space sharpness equals worst-case exactness while remaining weaker than family-pointwise exactness in general, and demonstrates that some existing Koopman-operator classification results achieve only the weaker form. The author supplies two upgrade results—an abstract pullback principle and a finite-query criterion—that turn the weaker exactness into the stronger one under suitable conditions, then introduces and studies a decoder-regular finite-query transport preorder on problems.

Core claim

The central claim is that exact SCI statements on families require a trichotomy of notions. Witness-space sharpness coincides with worst-case exactness, yet both are strictly weaker than family-pointwise exactness in general; certain Koopman-operator results are therefore sharp only in the worst-case sense. Two positive theorems—an abstract pullback principle and a concrete finite-query criterion—guarantee upgrades from witness-space sharpness to family-pointwise exactness. The decoder-regular finite-query transport preorder is shown to be a preorder with a transport-saturation sufficient criterion; its quotients fail to be upper semilattices on the full decoder classes but become upward and

What carries the argument

The trichotomy of family-pointwise exactness, witness-space sharpness, and worst-case exactness for SCI statements on families, together with the decoder-regular finite-query transport preorder that supplies saturation criteria for upgrades.

If this is right

Koopman-operator classification results remain sharp only in the worst-case sense rather than family-pointwise.
The abstract pullback principle converts witness-space sharpness into family-pointwise exactness for qualifying families.
The finite-query criterion supplies an explicit, checkable condition that achieves the upgrade.
The transport preorder on SCI problems satisfies the preorder axioms and admits a saturation sufficient criterion extending the principal-source package.
On nondegenerate subclasses of decoders the preorder is both upward and downward directed, while on the full classes the quotients are not upper semilattices.

Where Pith is reading between the lines

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

The same trichotomy of exactness notions may usefully apply to other computability or complexity frameworks beyond SCI when families rather than single objects are considered.
The transport preorder could serve as a tool to classify additional families of integration or spectral problems for which the strongest exactness is attainable.
Many existing SCI results stated for families may need re-checking to determine whether they reach family-pointwise exactness or stop at the weaker witness-space level.
The failure of the transport degrees to form a lattice in full generality indicates that the ordering structure on SCI problems is richer and less symmetric than a simple lattice would allow.

Load-bearing premise

The SCI framework and the chosen decoder classes are assumed to be well-defined for the families of problems under study, with the abstract pullback principle and finite-query criterion applying without extra hidden restrictions.

What would settle it

A concrete family of computational problems for which the SCI value satisfies witness-space sharpness and the finite-query criterion yet fails family-pointwise exactness, or a family where the transport preorder fails to be transitive.

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 \(\operatorname{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 show that certain Koopman-operator classification results are sharp only in this worst-case sense. 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.

Desk Editor's Note private letter to a colleague

This paper refines SCI exactness for families via a trichotomy and adds a decoder transport preorder with upgrade theorems that check out.

read the letter

The core contribution is spelling out three ways exactness can work when you have a family of problems instead of one: family-pointwise exactness, witness-space sharpness, and worst-case exactness. They prove the last two coincide but are strictly weaker than the first in general, and they give examples where some Koopman-operator results only reach the weaker level. That distinction is useful if you care about how SCI statements scale to families. They also supply two upgrade tools—an abstract pullback principle and a finite-query criterion—that let sharpness lift to pointwise exactness once the decoders meet regularity conditions. The decoder-regular finite-query transport preorder is defined, shown to be reflexive and transitive, equipped with a saturation criterion, and checked to avoid being a lattice in full generality while staying directed on the nondegenerate subclass. The integration and block-diagonal spectral families serve as concrete realizations. All of this rests on the standard SCI setup with no evident circularity or hidden restrictions. The non-lattice behavior is unsurprising for a preorder of this type and does not add much beyond the expected. The work stays inside the SCI literature, so the distinctions feel incremental outside that circle. A reader already working on solvability complexity indices or computability in functional analysis will get practical tools for sharpening statements and checking sharpness. It deserves a serious referee because the formalization is careful, the positive results are constructive, and the examples are natural. I would send it out for review.

Referee Report

0 major / 2 minor

Summary. The manuscript studies the formulation of exact Solvability Complexity Index (SCI) statements for families of computational problems. It distinguishes family-pointwise exactness, witness-space sharpness, and worst-case exactness; proves that witness-space sharpness coincides with worst-case exactness but is in general strictly weaker than family-pointwise exactness; establishes an abstract pullback principle and a finite-query criterion that upgrade witness-space sharpness to family-pointwise exactness; introduces a decoder-regular finite-query transport preorder on SCI problems, proves it is a preorder, derives a transport-saturation criterion, and shows the associated degrees need not form a lattice; analyzes the decoder classes R_cont and R_Bor (quotients not upper semilattices on the full class, but the preorder directed on the nondegenerate subclass); and exhibits two realizing families (exact integration on compact intervals and block-diagonal spectral decision).

Significance. If the results hold, the work supplies a precise trichotomy and upgrade mechanisms that clarify how sharpness statements should be phrased for families in the SCI framework. The transport preorder and saturation criterion extend existing principal-source techniques, while the non-lattice and directedness results highlight structural subtleties. The two concrete families demonstrate that the distinctions are realized in natural problems from analysis and operator theory, including sharpness of certain Koopman-operator classification results only in the worst-case sense. These contributions strengthen the conceptual toolkit for computable analysis and related fields.

minor comments (2)

[Introduction] The abstract is information-dense; a brief motivating example of the trichotomy (e.g., a simple family where witness-space sharpness holds but family-pointwise fails) placed early in the introduction would improve accessibility without lengthening the paper.
[Decoder-class analysis] Notation for the decoder classes R_cont and R_Bor is introduced cleanly, but a short table or diagram summarizing their lattice-theoretic properties across the full and nondegenerate classes would aid quick reference.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful and positive report, which accurately summarizes the manuscript's contributions to the trichotomy of exactness notions in the SCI framework for families, the upgrade principles, the decoder-regular transport preorder, and the realizing examples from integration and spectral decisions. The recommendation of minor revision is noted with appreciation.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The manuscript introduces fresh definitions for the trichotomy (family-pointwise exactness, witness-space sharpness, worst-case exactness) and proves their relations via explicit constructions, counterexamples, and direct verification on decoder classes. The abstract pullback principle, finite-query criterion, and transport preorder are established by standard arguments on the SCI setup without reducing any central claim to a fitted input, self-citation chain, or definitional tautology. All load-bearing steps rest on independent mathematical checks and external SCI foundations, yielding a fully self-contained derivation.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard set-theoretic and order-theoretic axioms for defining preorders and equivalence relations on computational problems; no free parameters or invented entities are introduced.

axioms (1)

standard math Standard axioms of set theory and order theory for preorders and equivalence relations
Invoked when defining the decoder-regular finite-query transport preorder and proving it is a preorder.

pith-pipeline@v0.9.0 · 5578 in / 1288 out tokens · 35629 ms · 2026-05-10T13:44:14.821285+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

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

[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]

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

2023
[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

1984
[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

2011
[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

1995
[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

2019
[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

2010
[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

1976
[9]

Solvability complexity index classification for koopman operator spectra in L ^p for 1< p<

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 arXiv 2025
[10]

Foundational analysis of the solvability complexity index: The weihrauch-sci intermediate hierarchy and a koopman operator example

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 arXiv 2026
[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

1988