← All papers
First page of Descent Before Hardness: Orbit-Gap Obstructions in Exact Certification

Descent Before Hardness: Orbit-Gap Obstructions in Exact Certification

Tristan Simas

cs.CC Apr 8, 2026 · v1
All numbered results mechanized in Lean 4, with a ledger mapping claims to formal identifiers.
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.

Exact certification has a quotient where states are equivalent when they have the same correct outputs. Syntactic tractability proxies can fail at the predicate level because correctness-preserving presentation moves may change the statistics they inspect. The question is when a proxy defines a property of the certification problem at all, prior to hardness questions.

Orbit gaps are identified as the complete obstruction: a proxy fails when one closure orbit contains both positive and negative presentations. Exact closure-invariant classification is possible if and only if the positive and negative orbit hulls are disjoint. Quotient-preserving normalizations and computable orbit catalogues yield positive results. All numbered results are mechanized in Lean 4.

Three binary-pairwise proxy families and one offset-normalization witness exhibit same-orbit disagreement in the finite-local regime. Positive results come from predicates defined directly on the correctness quotient, whose descended predicates compose under Boolean operations. The result complements the Rice-analog line of Borchert, Stephan, Hemaspaandra, and Rothe.