Descent Before Hardness: Orbit-Gap Obstructions in Exact Certification
Pith reviewed 2026-05-21 10:07 UTC · model grok-4.3
The pith
A uniform pair-targeted affine witness produces same-orbit disagreements that rule out exact structural classification on the full binary pairwise domain across four candidate criteria.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
Exact classification by closure-law-invariant predicates succeeds exactly when the target is constant on closure orbits; on a closure-closed domain this holds if and only if the positive and negative orbit hulls are disjoint, yielding a least exact closure-invariant classifier. Across four natural candidate structural tractability criteria a uniform pair-targeted affine witness produces same-orbit disagreements and thereby rules out exact structural classification on the full binary pairwise domain. Because the witness class already sits inside the universal semantic framework, any universal exact-certification theory whose structural tractability proxy restricts to these finite local predic
What carries the argument
The uniform pair-targeted affine witness that produces same-orbit disagreements under candidate structural tractability criteria.
Load-bearing premise
That the witness class already sits inside the universal semantic framework so the obstruction is inherited by any universal exact-certification theory whose structural tractability proxy restricts to finite local predicates.
What would settle it
A direct check that the pair-targeted affine witness fails to produce same-orbit disagreements for one or more of the four candidate criteria on the full binary pairwise domain.
Figures
read the original abstract
Exact certification has a quotient: states are equivalent when they have the same correct outputs. A tractability proxy must first define a predicate on this quotient before ordinary hardness or algorithmic questions arise. Raw syntactic proxies can fail at that earlier step, because correctness-preserving presentation moves may change the statistics they inspect while preserving the exact-certification problem. Orbit gaps are the complete obstruction. An orbit gap occurs when one closure orbit contains both positive and negative presentations of a target. Exact closure-invariant classification is possible if and only if the positive and negative orbit hulls are disjoint. When the hulls are disjoint, the closure hull is the least exact classifier. With computable orbit representatives, this hull classifier becomes a quotient-level algorithm. These are predicate-level results: they establish when a proxy defines a property of the certification problem at all, a precondition logically prior to class lower bounds on the resulting recovery task and deliberately not a substitute for them. The structural transfer applies to every fixed correctness relation, independent of whether that relation is polynomial-time accessible. In the direct finite-local regime, where local routing tests are computed from raw pairwise syntax, three binary-pairwise proxy families and one offset-normalization witness exhibit same-orbit disagreement. Positive results arise from quotient-preserving normalizations, computable orbit catalogues whose descended predicates compose under Boolean operations, and predicates defined directly on the correctness quotient. The result complements the Rice-analog line of Borchert, Stephan, Hemaspaandra, and Rothe. All numbered results are mechanized in Lean 4; the supplementary ledger maps each claim to its formal identifier.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript develops a universal semantic framework reducing exact relevance certification for decision, counting, search, approximation, PAC, randomized, and distributional problems to admissible-output quotient recovery via the relation s ~_R s' iff Adm_R(s) = Adm_R(s'). It identifies orbit gaps as the obstruction to exact classification by closure-law-invariant structural predicates, and proves that on closure-closed domains classification succeeds precisely when positive and negative orbit hulls are disjoint. The central technical claim is that a uniform pair-targeted affine witness on the full binary pairwise domain produces same-orbit disagreements for each of four natural candidate structural tractability criteria, thereby ruling out exact structural classification; because the witness class already lies inside the universal framework, any exact-certification theory whose structural proxy restricts to finite local predicates inherits the same obstruction.
Significance. If the witness construction and inheritance argument are verified, the result would establish a concrete limit on the power of closure-law-invariant structural predicates for exact tractability classification across a broad range of computational guarantees. The unification of disparate problem types under quotient recovery and the explicit identification of orbit gaps as the precise obstruction constitute a conceptual contribution that could influence how structural methods are applied in complexity theory. The paper supplies a reproducible witness class and a falsifiable prediction (same-orbit disagreement on the binary pairwise domain) that can be checked directly.
major comments (2)
- [Abstract / universal semantic framework definition] Abstract and the section defining the universal semantic framework: the inheritance claim—that any universal exact-certification theory whose structural tractability proxy restricts to finite local predicates inherits the obstruction—requires an explicit restriction map together with a proof that both witness admissibility and the same-orbit disagreements are preserved. The abstract states only that the witness “already sits inside” the framework; without invariance of orbits and admissibility under the restriction, the transfer does not follow.
- [Witness construction and four-criteria comparison] The paragraph introducing the uniform pair-targeted affine witness: the claim that this single witness produces same-orbit disagreements for all four candidate criteria must be accompanied by the explicit definitions of the four criteria, the affine witness, and the orbit computation showing the disagreements. If any of the four criteria is chosen in a way that excludes the witness or collapses the relevant orbits, the “rules out exact structural classification” conclusion is not supported.
minor comments (2)
- [Abstract] Notation: the symbol Adm_R is introduced without an explicit inductive definition or reference to its prior appearance; a short displayed definition would improve readability.
- [Closing paragraph] The final sentence on utility perturbations would benefit from a concrete example showing how an arbitrarily small perturbation flips relevance on the binary pairwise domain.
Simulated Author's Rebuttal
We thank the referee for the careful reading and constructive major comments. We agree that the inheritance argument and the witness paragraph can be strengthened for clarity while preserving the manuscript's core claims. We respond point by point below.
read point-by-point responses
-
Referee: [Abstract / universal semantic framework definition] Abstract and the section defining the universal semantic framework: the inheritance claim—that any universal exact-certification theory whose structural tractability proxy restricts to finite local predicates inherits the obstruction—requires an explicit restriction map together with a proof that both witness admissibility and the same-orbit disagreements are preserved. The abstract states only that the witness “already sits inside” the framework; without invariance of orbits and admissibility under the restriction, the transfer does not follow.
Authors: We accept that the inheritance claim benefits from an explicit treatment. In the revised manuscript we will add a dedicated paragraph (or short subsection) that defines the restriction map from the universal admissible-output framework to the finite local predicates on the binary pairwise domain. We will prove that (i) the pair-targeted affine witness remains admissible under the restriction and (ii) the same-orbit disagreements are preserved because the relevant orbits are computed inside the restricted subdomain and are therefore invariant. This will make the transfer to any structural proxy that restricts to these predicates fully rigorous. revision: yes
-
Referee: [Witness construction and four-criteria comparison] The paragraph introducing the uniform pair-targeted affine witness: the claim that this single witness produces same-orbit disagreements for all four candidate criteria must be accompanied by the explicit definitions of the four criteria, the affine witness, and the orbit computation showing the disagreements. If any of the four criteria is chosen in a way that excludes the witness or collapses the relevant orbits, the “rules out exact structural classification” conclusion is not supported.
Authors: The four candidate criteria (closure-law-invariant predicates, positive/negative orbit hulls, least exact classifier, and the two hull-disjointness conditions) are already defined in the sections immediately preceding the witness paragraph, and the uniform pair-targeted affine witness is constructed to lie inside the admissible-output relation on the full binary pairwise domain. To address the referee’s concern we will revise the introducing paragraph to include a concise recap of the four criteria together with a brief sketch of the orbit computation for each, exhibiting the same-orbit disagreements explicitly. We maintain that the witness was chosen precisely so that it intersects the orbits non-trivially for all four criteria simultaneously; none of them excludes the witness or collapses the relevant orbits. revision: partial
Circularity Check
Self-referential placement of witness inside defined universal framework enables inheritance claim by construction
specific steps
-
self definitional
[Abstract]
"Because that witness class already sits inside the universal semantic framework, any universal exact-certification theory whose structural tractability proxy restricts to these finite local predicates inherits the same obstruction on that witness class."
The universal semantic framework is introduced as identifying admissible-output quotient recovery as the canonical object over all such relations; placing the specific witness inside it by this definition then directly yields the inheritance of the obstruction for restricting proxies, without an explicit restriction map or proof that same-orbit disagreements remain invariant.
full rationale
The derivation shows an independent witness construction producing same-orbit disagreements on the full binary pairwise domain under four candidate criteria. However, the load-bearing inheritance step for any universal exact-certification theory rests on the witness class already sitting inside the universal semantic framework, which the paper itself defines in terms of admissible-output quotient recovery and the relations under analysis. This creates a mild self-definitional loop for the restriction-invariance claim, as no separate verification of orbit preservation or admissibility under the finite-local-predicate restriction is exhibited. The core obstruction result on the unrestricted domain remains non-circular.
Axiom & Free-Parameter Ledger
axioms (2)
- domain assumption Any rigorously specified problem determines an admissible-output relation R.
- domain assumption Exact relevance certification depends only on the induced decision quotient relation.
invented entities (2)
-
orbit gaps
no independent evidence
-
uniform pair-targeted affine witness
no independent evidence
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.