Computational Complexity of Sufficiency in Decision Problems

Tristan Simas · 2026

Read Computational Complexity of Sufficiency in Decision Problems 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-2601-15571.txt.

Introduction

Tristan Simas studies how hard it is to judge sufficiency in decisions in a 2026 arXiv paper. The setting is a formal decision problem. An action set, a state space, and a utility function define it. The state space is a product of coordinates. A set of coordinates is sufficient when it pins down the optimal action. If two states agree on those coordinates, they share the same best action.

Simas characterizes the computational complexity of that judgment. In plain terms, he asks how costly it is to test whether a coordinate set suffices. The answer guides anyone who wants to trim inputs to a decision rule. Fewer needed coordinates mean simpler, cheaper decisions. Complexity bounds tell us when that trimming is feasible and when it is hopeless.

Catalog record

CREATORTristan Simas
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE52 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-15571

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Computational Complexity of Sufficiency in Decision Problems Tristan Simas Abstract We characterize the computational complexity of coordinate sufficiency in decision problems within the formal model. Given action set A A , state space S = X 1 × ⋯ × X n S=X_{1}\times\cdots\times X_{n} , and utility u : A × S → ℝ u:A\times S\to\mathbb{R} , a coordinate set I I is sufficient if s I = s I ′ ⟹ Opt ​ ( s ) = Opt ​ ( s ′ ) s_{I}=s^{\prime}_{I}\implies\text{Opt}(s)=\text{Opt}(s^{\prime}) . The landscape in the formal model: • General case: SUFFICIENCY-CHECK is coNP -complete; ANCHOR-SUFFICIENCY is Σ 2 P \Sigma_{2}^{\textsf{P}} -complete. • Tractable cases: Polynomial-time for bounded action sets under the explicit-state encoding; separable utilities ( u = f + g u=f+g ) under any encoding; and tree-structured utility with explicit local factors. • Encoding-regime separation: Polynomial-time under the explicit-state encoding (polynomial in | S | |S| ). Under ETH, there exist succinctly encoded worst-case instances witnessed by a strengthened gadget construction (mechanized in Lean; see Appendix A ) with k ∗ = n k^{*}=n for which SUFFICIENCY-CHECK requires 2 Ω ⁡ ( n ) 2^{\Omega(n)} time. The tractable cases are stated with explicit encoding assumptions (Section 2.4 ). Together, these results answer the question “when is decision-relevant information identifiable efficiently?” within the stated regimes. The primary contribution is theoretical: a complete characterization of the core decision-relevant problems in the formal model (coNP/ Σ 2 P \Sigma_{2}^{P} completeness and tractable cases under explicit encoding assumptions). The practical corollaries follow from these theorems. The reduction constructions and key equivalence theorems are machine-checked in Lean 4 ( ∼ \sim 5,000 lines, 200+ theorems); complexity classifications follow by composition with standard results (see Appendix A ). Keywords: computational complexity, decision theory, polynomial hierarchy, tractability dichotomy, Lean 4 † † footnotetext: © 2026 Tristan Simas. This work is licensed under CC BY 4.0. License: https://creativecommons.org/licenses/by/4.0/ Zenodo DOI: 10.5281/zenodo.18140965 1 Introduction Consider a decision problem with actions A and states S=X_{1}\times\cdots\times X_{n} . A coordinate set I\subseteq\{1,\ldots,n\} is sufficient if knowing only coordinates in I determines the optimal action: s_{I}=s^{\prime}_{I}\implies\text{Opt}(s)=\text{Opt}(s^{\prime}) This paper characterizes the efficient cases of coordinate sufficiency within the formal model: Section 2.4 fixes the computational model and input encodings used for all complexity claims. Problem Complexity When Tractable SUFFICIENCY-CHECK coNP -complete Bounded actions (explicit-state), separable utility, tree-structured utility MINIMUM-SUFFICIENT-SET coNP -complete Same conditions ANCHOR-SUFFICIENCY \Sigma_{2}^{\textsf{P}} -complete Open The tractable cases are stated with explicit encoding assumptions (Section 2.4 ). Outside those regimes, the succinct model yields hardness. 1.1 Landscape Summary When is sufficiency checking tractable? We identify three sufficient conditions: 1. Bounded actions ( |A|\leq k ) under explicit-state encoding: with constantly many actions, we enumerate action pairs over the explicit utility table. 2. Separable utility ( u(a,s)=f(a)+g(s) ): The optimal action depends only on f , making all coordinates irrelevant to the decision. 3. Tree-structured utility : With explicit local factors over a tree, dynamic programming yields polynomial algorithms in the input length. Each condition is stated with its encoding assumption. Outside these regimes, the general problem remains coNP -hard (Theorem 3.6 ). When is it intractable? The general problem is coNP -complete (Theorem 3.6 ), with a separation between explicit-state tractability and succinct worst-case hardness: • In the explicit-state model: SUFFICIENCY-CHECK is solvable in polynomial time in |S| by explicitly computing \text{Opt}(s) for all s\in S and checking all pairs (s,s^{\prime}) with equal I -projection. In particular, instances with k^{*}=O(\log|S|) are tractable in this model. • In the succinct model: under ETH there exist worst-case instances produced by our strengthened gadget in which the minimal sufficient set has size \Omega(n) (indeed n ) and SUFFICIENCY-CHECK requires 2^{\Omega(n)} time. The lower-bound statement does not address intermediate regimes. 1.2 Main Theorems 1. Theorem 3.6 : SUFFICIENCY-CHECK is coNP -complete via reduction from TAUTOLOGY. 2. Theorem 3.7 : MINIMUM-SUFFICIENT-SET is coNP -complete (the \Sigma_{2}^{\textsf{P}} structure collapses). 3. Theorem 3.9 : ANCHOR-SUFFICIENCY is \Sigma_{2}^{\textsf{P}} -complete via reduction from \exists\forall -SAT. 4. Theorem 4.1 : Encoding-regime separation: explicit-state polynomial-time (polynomial in |S| ), and under ETH a succinct worst-case lower bound witnessed by a hard family with k^{*}=n . 5. Theorem 5.1 : Polynomial algorithms for bounded actions, separable utility, tree structure. 1.3 Machine-Checked Proofs The reduction constructions and key equivalence theorems are machine-checked in Lean 4 [ 6 ] ( \sim 5,000 lines, 200+ theorems). The formalization verifies that the TAUTOLOGY reduction correctly maps tautologies to sufficient coordinate sets. Complexity class membership (coNP-completeness, \Sigma_{2}^{P} -completeness) follows by composition with standard complexity-theoretic results. What is new. We contribute (i) formal definitions of decision-theoretic sufficiency in Lean; (ii) machine-checked proofs of reduction correctness for the TAUTOLOGY and \exists\forall -SAT reductions; and (iii) a complete complexity landscape for coordinate sufficiency with explicit encoding assumptions. Prior work establishes hardness informally; we formalize the constructions. 1.4 Paper Structure The primary contribution is theoretical: a formalized reduction framework and a complete characterization of the core decision-relevant problems in the formal model (coNP/ \Sigma_{2}^{P} completeness and tractable cases stated under explicit encoding assumptions). Sections 3 – 5 contain the core theorems. Section 2 : foundations. Section 3 : hardness proofs. Section 4 : dichotomy. Section 5 : tractable cases. Sections 7 and 8 : corollaries and implications for practice. Section 9 : related work. Appendix A : Lean listings. 2 Formal Foundations We formalize decision problems with coordinate structure, sufficiency of coordinate sets, and the decision quotient, drawing on classical decision theory [ 12 , 11 ] . 2.1 Decision Problems with Coordinate Structure Definition 2.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 2.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 2.3 (Optimizer Map) . For state s\in S , the optimal action set is: \text{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)\} 2.2 Sufficiency and Relevance Definition 2.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\text{Opt}(s)=\text{Opt}(s^{\prime}) Equivalently, the optimal action depends only on coordinates in I . Definition 2.5 (Minimal Sufficient Set) . A sufficient set I is minimal if no proper subset I^{\prime}\subsetneq I is sufficient. Definition 2.6 (Relevant Coordinate) . Coordinate i is relevant if it belongs to some minimal sufficient set. Example 2.7 (Weather Decision) . Consider deciding whether to carry an umbrella: • Actions: A=\{\text{carry},\text{don't carry}\} • Coordinates: X_{1}=\{\text{rain},\text{no rain}\} , X_{2}=\{\text{hot},\text{cold}\} , X_{3}=\{\text{Monday},\ldots,\text{Sunday}\} • Utility: U(\text{carry},s)=-1+3\cdot\mathbf{1}[s_{1}=\text{rain}] , U(\text{don't carry},s)=-2\cdot\mathbf{1}[s_{1}=\text{rain}] The minimal sufficient set is I=\{1\} (only rain forecast matters). Coordinates 2 and 3 (temperature, day of week) are irrelevant. 2.3 The Decision Quotient Definition 2.8 (Decision Equivalence) . For coordinate set I , states s,s^{\prime} are I -equivalent (written s\sim_{I}s^{\prime} ) if s_{I}=s^{\prime}_{I} . Definition 2.9 (Decision Quotient) . The decision quotient for state s under coordinate set I is: \text{DQ}_{I}(s)=\frac{|\{a\in A:a\in\text{Opt}(s^{\prime})\text{ for some }s^{\prime}\sim_{I}s\}|}{|A|} This measures the fraction of actions that are optimal for at least one state consistent with I . Proposition 2.10 (Sufficiency Characterization) . Coordinate

Read the complete text