The Optimizer Quotient and the Certification Trilemma
Tristan Simas · 2026
Read The Optimizer Quotient and the Certification Trilemma by Tristan Simas (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-14689.txt.
Introduction
Simas proves a certification trilemma for the optimizer quotient in exact decision problems. The quotient is the coarsest abstraction that keeps all decision-relevant information. Certifying its coordinate structure exactly hits a three-way wall. If P differs from coNP, no certifier can be sound, complete and cheap at once. Costs shift by regime: coNP, PP-hard and PSPACE-complete cases appear. Six structural limits restore polynomial-time certification. The finite core of the proof is mechanized in Lean 4.
Catalog record
| CREATOR | Tristan Simas |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 135177 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.14689
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The Optimizer Quotient and the Certification Trilemma Tristan Simas Abstract The optimizer quotient is the canonical object for exact decision-relevant information: it is the coarsest exact decision-preserving abstraction (Theorem 2.15). This paper proves that exact certification of this object’s coordinate structure is subject to an impossibility trilemma: under P ≠ coNP \mathrm{P}\neq\mathrm{coNP} , no certifier can be simultaneously sound, complete on all in-scope instances, and polynomial-budgeted (Theorem 7.1). The cost of this impossibility varies by regime: coNP (static), PP-hard (stochastic decisiveness), PSPACE-complete (sequential). Six structural restrictions collapse certification to polynomial time. The finite reduction and verification core is mechanized in Lean 4. I Introduction I-A The Optimizer Quotient: A Canonical Object Exact decision-preserving information has a canonical form: the optimizer quotient. For a finite coordinate-structured decision problem \mathcal{D}=(A,S,U) with S=X_{1}\times\cdots\times X_{n} , the optimizer quotient identifies states exactly when they induce the same optimal-action set \mathrm{Opt}(s) . This quotient is the coarsest exact decision-preserving abstraction (Theorem II.15 ): every surjective abstraction that preserves optimal actions factors uniquely through it. Equivalently, in Set , it is the coimage/image factorization of the optimizer map. This canonical object exists for every decision problem and unifies separate literatures. In rough-set theory, attribute reduction asks which coordinates preserve decision distinctions; in constraint satisfaction, backdoor sets identify variables whose fixation yields tractability; in feature selection, minimal sufficient subsets are sought; in MDP abstraction, state aggregation preserves value or policy structure. The optimizer quotient provides a common mathematical foundation: it is the canonical object for exact relevance in all these settings. I-B The Certification Trilemma: An Impossibility Theorem From the optimizer quotient we derive a structural constraint on exact certifiers. Under \mathrm{P}\neq\mathrm{coNP} , no solver can be simultaneously integrity-preserving, non-abstaining on all in-scope instances, and polynomial-budgeted (Theorem 7.1). This impossibility yields a trilemma: any exact certifier in the hard regime must either abstain on some instances, weaken its guarantee, or risk overclaiming. The trilemma is not merely a restatement of coNP-hardness; it is a certified-solver impossibility result with operational consequences for systems claiming exact reliability. I-C The Complexity Map as Evidence The impossibility manifests differently across regimes. The static regime yields coNP-completeness for base and minimum queries (via relevance containment), while static anchor sufficiency is \Sigma_{2}^{P} -complete. In the stochastic regime, the problem splits: preservation bridges to static sufficiency (polynomial-time under explicit encoding), while decisiveness is PP-hard under succinct encoding. In the sequential regime, temporal contingency lifts all queries to PSPACE-complete. These classifications form a regime-sensitive complexity matrix (Table III ) that shows the impossibility’s reach expanding with model expressiveness. Two narrow cells in the stochastic-preservation row (general distributions, without the full-support assumption) remain open; these are explicitly marked as scope boundaries in Table II and do not affect any of the proved results, the optimizer quotient, the certification trilemma, or the completeness of the static, sequential, and stochastic-decisiveness regimes. I-D Tractable Boundaries Six structural restrictions collapse exact certification to polynomial time: bounded actions, separable utility, low tensor rank, tree structure, bounded treewidth, and coordinate symmetry. Each removes a distinct source of hardness, providing tractable boundaries to the impossibility theorem. I-E Mechanized Core A Lean 4 artifact mechanically checks the optimizer-quotient universal property, finite deciders, reduction-correctness lemmas, witness schemas, and bridge results 1 1 1 Lean: QT1 , QT7 , DC91-99 , OU1-2 , OU8-12 , EH1-10 . The 22K-line artifact verifies the combinatorial core, while oracle-class placements are argued in the paper text. I-F Paper Structure Section II introduces the formal setup. Sections III , IV , and V develop the static, stochastic, and sequential complexity classifications. Section VI consolidates them into the regime matrix. Section 7 presents the impossibility theorem and trilemma. Section 8 collects structural consequences. Sections VII and VIII cover encoding contrasts and tractable cases. Section 9 situates the work, and Appendix B collects model translations. I-G Artifact Availability The proof artifact is archived at https://doi.org/10.5281/zenodo.19057595 . The cited-content snapshot contains 22068 lines across 67 files with 0 occurrences of sorry . II Formal Setup This section fixes the abstract vocabulary used throughout the paper. We work with finite decision problems whose state spaces factor into coordinates, and we isolate the minimal terminology needed to state the later complexity results. The same setup will support the paper’s three core regime classifications, the encoding-sensitive boundary, and the later consequence sections. Object Quantifier shape Certifies Role SUFFICIENCY-CHECK universal over state pairs exact coordinate sufficiency baseline certification predicate MINIMUM-SUFFICIENT-SET apparent \exists I\,\forall(s,s^{\prime}) check smallest sufficient support collapses to relevance containment in static regime ANCHOR-SUFFICIENCY \exists anchor, then universal fiber check exact preservation on one chosen fiber retains the outer existential layer Optimizer quotient universal factorization property coarsest decision-preserving abstraction canonical structural object TABLE I: Setup map. The four central objects differ mainly in quantifier shape: minimum sufficiency collapses in the static regime, while anchor sufficiency keeps its existential fiber choice. II-A Decision Problems with Coordinate Structure Definition II.1 (Decision Problem). A decision problem with coordinate structure is a tuple \mathcal{D}=(A,X_{1},\ldots,X_{n},U) where: • A is a finite set of actions (alternatives) • X_{1},\ldots,X_{n} are finite coordinate spaces • S=X_{1}\times\cdots\times X_{n} is the state space • U:A\times S\to\mathbb{Q} is the utility function Definition II.2 (Projection). For state s=(s_{1},\ldots,s_{n})\in S and coordinate set I\subseteq\{1,\ldots,n\} : s_{I}:=(s_{i})_{i\in I} is the projection of s onto coordinates in I . Definition II.3 (Optimizer Map). For state s\in S , the optimal action set is: \mathrm{Opt}(s):=\arg\max_{a\in A}U(a,s)=\{a\in A:U(a,s)=\max_{a^{\prime}\in A}U(a^{\prime},s)\} II-B Sufficiency and Relevance Definition II.4 (Sufficient Coordinate Set). A coordinate set I\subseteq\{1,\ldots,n\} is sufficient for decision problem \mathcal{D} if: \forall s,s^{\prime}\in S:\quad s_{I}=s^{\prime}_{I}\implies\mathrm{Opt}(s)=\mathrm{Opt}(s^{\prime}) Equivalently, the optimal action depends only on coordinates in I . Proposition II.5 † † footnotemark: † † footnotetext: : DP6 (Empty-Set Sufficiency Equals Constant Decision Boundary). The empty set \emptyset is sufficient if and only if \mathrm{Opt}(s) is constant over the entire state space. Proof. If \emptyset is sufficient, then every two states agree on their empty projection, so sufficiency forces \mathrm{Opt}(s)=\mathrm{Opt}(s^{\prime}) for all s,s^{\prime}\in S . The converse is immediate. \blacksquare Proposition II.6 † † footnotemark: † † footnotetext: : DP7 (Insufficiency Equals Counterexample Witness). Coordinate set I is not sufficient if and only if there exist states s,s^{\prime}\in S such that s_{I}=s^{\prime}_{I} but \mathrm{Opt}(s)\neq\mathrm{Opt}(s^{\prime}) . Proof. This is the direct negation of Definition II.4 . \blacksquare Definition II.7 (Minimal Sufficient Set). A sufficient set I is minimal if no proper subset I^{\prime}\subsetneq I is sufficient. Definition II.8 (Relevant Coordinate). Coordinate i is relevant if there exist states that differ only at coordinate i and induce different optimal-action sets: i\text{ is relevant}\iff\exists s,s^{\prime}\in S:\;\Big(\forall j\neq i,\;s_{j}=s^{\prime}_{j}\Big)\ \wedge\ \mathrm{Opt}(s)\neq\mathrm{Opt}(s^{\prime}). Proposition II.9 † † footnotemark: † † footnotetext: : DP1-2 (Minimal-Set/Relevance Equivalence). For any minimal sufficient set I and any coordinate i , i\in I\iff i\text{ is relevant}. Hence every minimal sufficient set is exactly the relevant-coordinate set. Proof. If i\in I were not relevant, then changing coordinate i while keeping all others fixed would never alter the optimal-action set, so removing i would preserve sufficiency, contradicting minimality. Conversely, every sufficient set must contain each relevant coordinate, because omitting a relevant coordinate leaves a witness pair with identical I -projection but different optimal-action sets. \blacksquare Definition II.10 (Exact Relevance Identifiability). For a decision problem \mathcal{D} and candidate set I ,