Decision Quotient: A Regime-Sensitive Complexity Theory of Exact Relevance Certification
This work addresses a foundational problem in complexity theory for AI and decision-making, providing exact relevance certification with regime-sensitive hardness classifications.
The paper tackles the problem of determining which coordinates of a decision problem can be hidden while preserving decision relevance, classifying the computational hardness of certifying this structure across static, stochastic, and sequential regimes, with results including coNP-completeness in static, PP-hardness in stochastic, and PSPACE-completeness in sequential settings.
Which 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.