{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreif437zn7nthd3u2vm7l3oana63enplnmdznqxffepl5b23gtqa4vu",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mh7zibh5wrh2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2603.14689v1",
  "publishedAt": "2026-03-17T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Tristan Simas"
  ],
  "textContent": "**Authors:** Tristan Simas\n\nWhich coordinates of a decision problem can be hidden without changing the decision, and what is the coarsest exact abstraction that preserves all decision-relevant distinctions? We study this as an exact relevance-certification problem organized around the optimizer quotient. We classify how hard it is to certify this structure across three settings: static (counterexample exclusion), stochastic (conditioning and expectation), and sequential (temporal structure). In the static regime, sufficiency collapses to relevance containment, so minimum sufficiency is coNP-complete. In the stochastic regime, preservation and decisiveness separate: preservation is polynomial-time under explicit-state encoding with bridge theorems to static sufficiency and the optimizer quotient, while decisiveness is PP-hard under succinct encoding with anchor and minimum variants in $\\textsf{NP}^{\\textsf{PP}}$. In the sequential regime, all queries are PSPACE-complete. We also prove an encoding-sensitive contrast between explicit-state tractability and succinct-encoding hardness, derive an integrity-competence trilemma, and isolate twelve tractable subcases. A Lean 4 artifact mechanically verifies the optimizer-quotient universal property, main reductions, and finite decider core.",
  "title": "Decision Quotient: A Regime-Sensitive Complexity Theory of Exact Relevance Certification"
}