{"ID":2823729,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.24860","arxiv_id":"2512.24860","title":"Approximate Computation via Le Cam Simulability","abstract":"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). We formally define computational deficiency ($δ_{\\text{poly}}$) and use it to construct the complexity class LeCam-P (Decision-Robust Polynomial Time), characterizing problems that may be syntactically hard but semantically easy to approximate. 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, bridging the gap between algorithmic complexity and decision theory.","short_abstract":"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 ap...","url_abs":"https://arxiv.org/abs/2512.24860","url_pdf":"https://arxiv.org/pdf/2512.24860v1","authors":"[\"Deniz Akdemir\"]","published":"2025-12-31T13:40:02Z","proceeding":"math.ST","tasks":"[\"math.ST\",\"cs.CC\",\"cs.IT\"]","methods":"[]","has_code":false}