We propose a decision-theoretic framework for computational complexity, complementary to classical theory: moving from syntactic exactness (Turing / Shannon) to semantic simulability (Le Cam). While classical theory classifies problems by the cost of exact solution, modern computation often seeks only decision-valid approximations. We introduce a framework where "computation" is viewed as the efficient simulation of a target statistical experiment within a bounded risk distortion (Le Cam deficiency). Our notion of simulability is operational and decision-relative: we do not assume any asymptotic identification of complexity classes, and we do not interpret such identifications as ontological continuity claims in the finite regime. Our guarantees are stated relative to an -tolerance and bounded decision losses; asymptotic analogies are motivational only. We define computational deficiency (₎₋ₘ) and use it to construct the complexity class LeCam-P (Decision-Robust Polynomial Time), characterizing problems that may be hard to solve exactly but easy to approximate in a semantic sense. We show that classical Karp reductions can be viewed as zero-deficiency simulations, and that approximate reductions correspond to bounded deficiency. Furthermore, we establish the No-Free-Transfer Inequality, showing that strictly invariant representations inevitably destroy decision-relevant information. This framework offers a statistical perspective on approximation theory and helps formalize why heuristic or learned solvers can be decision-valid on hard combinatorial problems (e. g. , the traveling salesperson problem or protein folding) despite failing to compute exact solutions. The introduction summarizes the main contributions and provides a roadmap.
Deniz Akdemir (Sun,) studied this question.