AUTO-GENERATED COPY/PASTE METADATA
Generated: 2026-04-28T11:59:18.954475

=== HUMAN COPY/PASTE ===

Title: Exact Structural Abstraction and Tractability Limits

Abstract (Unicode, for Zenodo):
Any rigorously specified problem determines an admissible-output relation R, and exact correctness depends only on the induced decision quotient relation s∼_Rs′ ⇔ Adm_R(s) = Adm_R(s′). Exact relevance certification asks which coordinates recover those classes. Decision, counting, search, approximation, PAC/regret/risk, randomized-output guarantees, anytime or finite-horizon guarantees, and distributional guarantees all reduce to this quotient-recovery problem.

Universal exact-semantics reduction identifies admissible-output quotient recovery as the canonical object. Optimizer-quotient realizability is maximal, so quotient shape alone cannot mark a tractability frontier. Orbit gaps are the exact obstruction to classification by closure-law-invariant structural predicates.

Exact classification by closure-law-invariant predicates succeeds exactly when the target is constant on closure orbits; on a closure-closed domain, equivalently, when the positive and negative orbit hulls are disjoint, in which case there is a least exact closure-invariant classifier. Across four natural candidate structural tractability criteria, a uniform pair-targeted affine witness produces same-orbit disagreements and rules out exact structural classification on the full binary pairwise domain. Because that witness class already sits inside the universal semantic framework, the same obstruction applies to any universal exact-certification characterization over rigorously specified problems. Restricting the domain helps only by removing orbit gaps. Without explicit margin control, arbitrarily small utility perturbations can flip relevance and sufficiency.

Abstract (MathJax, for arXiv):
Any rigorously specified problem determines an admissible-output relation $R$, and exact correctness depends only on the induced decision quotient relation $s \sim_R s' \iff \operatorname{Adm}_R(s)=\operatorname{Adm}_R(s')$. Exact relevance certification asks which coordinates recover those classes. Decision, counting, search, approximation, PAC/regret/risk, randomized-output guarantees, anytime or finite-horizon guarantees, and distributional guarantees all reduce to this quotient-recovery problem.

Universal exact-semantics reduction identifies admissible-output quotient recovery as the canonical object. Optimizer-quotient realizability is maximal, so quotient shape alone cannot mark a tractability frontier. Orbit gaps are the exact obstruction to classification by closure-law-invariant structural predicates.

Exact classification by closure-law-invariant predicates succeeds exactly when the target is constant on closure orbits; on a closure-closed domain, equivalently, when the positive and negative orbit hulls are disjoint, in which case there is a least exact closure-invariant classifier. Across four natural candidate structural tractability criteria, a uniform pair-targeted affine witness produces same-orbit disagreements and rules out exact structural classification on the full binary pairwise domain. Because that witness class already sits inside the universal semantic framework, the same obstruction applies to any universal exact-certification characterization over rigorously specified problems. Restricting the domain helps only by removing orbit gaps. Without explicit margin control, arbitrarily small utility perturbations can flip relevance and sufficiency.

arXiv Comments:
TheoretiCS submission. Main PDF: 38 pages, 4 tables. Supplementary: 12 pages, 2 tables. Lean 4 artifact: 23415 lines, 1097 theorems/lemmas across 73 files (0 sorry placeholders).

=== MACHINE YAML ===
paper_id: paper4d
title: Exact Structural Abstraction and Tractability Limits
zenodo:
  title: Exact Structural Abstraction and Tractability Limits
  abstract: 'Any rigorously specified problem determines an admissible-output relation
    R, and exact correctness depends only on the induced decision quotient relation
    s∼_Rs′ ⇔ Adm_R(s) = Adm_R(s′). Exact relevance certification asks which coordinates
    recover those classes. Decision, counting, search, approximation, PAC/regret/risk,
    randomized-output guarantees, anytime or finite-horizon guarantees, and distributional
    guarantees all reduce to this quotient-recovery problem.


    Universal exact-semantics reduction identifies admissible-output quotient recovery
    as the canonical object. Optimizer-quotient realizability is maximal, so quotient
    shape alone cannot mark a tractability frontier. Orbit gaps are the exact obstruction
    to classification by closure-law-invariant structural predicates.


    Exact classification by closure-law-invariant predicates succeeds exactly when
    the target is constant on closure orbits; on a closure-closed domain, equivalently,
    when the positive and negative orbit hulls are disjoint, in which case there is
    a least exact closure-invariant classifier. Across four natural candidate structural
    tractability criteria, a uniform pair-targeted affine witness produces same-orbit
    disagreements and rules out exact structural classification on the full binary
    pairwise domain. Because that witness class already sits inside the universal
    semantic framework, the same obstruction applies to any universal exact-certification
    characterization over rigorously specified problems. Restricting the domain helps
    only by removing orbit gaps. Without explicit margin control, arbitrarily small
    utility perturbations can flip relevance and sufficiency.'
arxiv:
  title: Exact Structural Abstraction and Tractability Limits
  abstract: 'Any rigorously specified problem determines an admissible-output relation
    $R$, and exact correctness depends only on the induced decision quotient relation
    $s \sim_R s'' \iff \operatorname{Adm}_R(s)=\operatorname{Adm}_R(s'')$. Exact relevance
    certification asks which coordinates recover those classes. Decision, counting,
    search, approximation, PAC/regret/risk, randomized-output guarantees, anytime
    or finite-horizon guarantees, and distributional guarantees all reduce to this
    quotient-recovery problem.


    Universal exact-semantics reduction identifies admissible-output quotient recovery
    as the canonical object. Optimizer-quotient realizability is maximal, so quotient
    shape alone cannot mark a tractability frontier. Orbit gaps are the exact obstruction
    to classification by closure-law-invariant structural predicates.


    Exact classification by closure-law-invariant predicates succeeds exactly when
    the target is constant on closure orbits; on a closure-closed domain, equivalently,
    when the positive and negative orbit hulls are disjoint, in which case there is
    a least exact closure-invariant classifier. Across four natural candidate structural
    tractability criteria, a uniform pair-targeted affine witness produces same-orbit
    disagreements and rules out exact structural classification on the full binary
    pairwise domain. Because that witness class already sits inside the universal
    semantic framework, the same obstruction applies to any universal exact-certification
    characterization over rigorously specified problems. Restricting the domain helps
    only by removing orbit gaps. Without explicit margin control, arbitrarily small
    utility perturbations can flip relevance and sufficiency.'
  comments: 'TheoretiCS submission. Main PDF: 38 pages, 4 tables. Supplementary: 12
    pages, 2 tables. Lean 4 artifact: 23415 lines, 1097 theorems/lemmas across 73
    files (0 sorry placeholders).'
abstract_variants:
  unicode: 'Any rigorously specified problem determines an admissible-output relation
    R, and exact correctness depends only on the induced decision quotient relation
    s∼_Rs′ ⇔ Adm_R(s) = Adm_R(s′). Exact relevance certification asks which coordinates
    recover those classes. Decision, counting, search, approximation, PAC/regret/risk,
    randomized-output guarantees, anytime or finite-horizon guarantees, and distributional
    guarantees all reduce to this quotient-recovery problem.


    Universal exact-semantics reduction identifies admissible-output quotient recovery
    as the canonical object. Optimizer-quotient realizability is maximal, so quotient
    shape alone cannot mark a tractability frontier. Orbit gaps are the exact obstruction
    to classification by closure-law-invariant structural predicates.


    Exact classification by closure-law-invariant predicates succeeds exactly when
    the target is constant on closure orbits; on a closure-closed domain, equivalently,
    when the positive and negative orbit hulls are disjoint, in which case there is
    a least exact closure-invariant classifier. Across four natural candidate structural
    tractability criteria, a uniform pair-targeted affine witness produces same-orbit
    disagreements and rules out exact structural classification on the full binary
    pairwise domain. Because that witness class already sits inside the universal
    semantic framework, the same obstruction applies to any universal exact-certification
    characterization over rigorously specified problems. Restricting the domain helps
    only by removing orbit gaps. Without explicit margin control, arbitrarily small
    utility perturbations can flip relevance and sufficiency.'
  mathjax: 'Any rigorously specified problem determines an admissible-output relation
    $R$, and exact correctness depends only on the induced decision quotient relation
    $s \sim_R s'' \iff \operatorname{Adm}_R(s)=\operatorname{Adm}_R(s'')$. Exact relevance
    certification asks which coordinates recover those classes. Decision, counting,
    search, approximation, PAC/regret/risk, randomized-output guarantees, anytime
    or finite-horizon guarantees, and distributional guarantees all reduce to this
    quotient-recovery problem.


    Universal exact-semantics reduction identifies admissible-output quotient recovery
    as the canonical object. Optimizer-quotient realizability is maximal, so quotient
    shape alone cannot mark a tractability frontier. Orbit gaps are the exact obstruction
    to classification by closure-law-invariant structural predicates.


    Exact classification by closure-law-invariant predicates succeeds exactly when
    the target is constant on closure orbits; on a closure-closed domain, equivalently,
    when the positive and negative orbit hulls are disjoint, in which case there is
    a least exact closure-invariant classifier. Across four natural candidate structural
    tractability criteria, a uniform pair-targeted affine witness produces same-orbit
    disagreements and rules out exact structural classification on the full binary
    pairwise domain. Because that witness class already sits inside the universal
    semantic framework, the same obstruction applies to any universal exact-certification
    characterization over rigorously specified problems. Restricting the domain helps
    only by removing orbit gaps. Without explicit margin control, arbitrarily small
    utility perturbations can flip relevance and sufficiency.'
