Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2601.15571 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917307771518976 |
|---|---|
| author | Simas, Tristan |
| author_facet | Simas, Tristan |
| contents | We characterize which coordinates of a factored state space determine optimal actions. For $\mathcal{D}=(A,S,U)$ with $S=X_1\times\cdots\times X_n$, coordinate set $I$ is sufficient if $s_I=s'_I\Rightarrow\operatorname{Opt}(s)=\operatorname{Opt}(s')$. The decision quotient $Q=S/{\sim}$ ($s\sim s'\Leftrightarrow\operatorname{Opt}(s)=\operatorname{Opt}(s')$) is the minimal abstraction: any abstraction preserving optimal actions factors uniquely through $Q$.
We prove fourteen first-principles theorems (thirteen from pure mathematics, one empirical). The chain from counting measure to probability to Bayes' theorem to $Q$ follows from finite set cardinality. Fisher information, entropy, optimal transport, rate-distortion, and thermodynamics each independently recover $\mathrm{srank}$ as decision complexity measure. From $\log x\leq x-1$ alone, Bayesian updating uniquely minimizes expected log loss.
Complexity: SUFFICIENCY-CHECK and MINIMUM-SUFFICIENT-SET are coNP-complete; ANCHOR-SUFFICIENCY is $Σ_2^P$-complete; stochastic and sequential variants PP- and PSPACE-complete with strict separation. Six subcases admit polynomial algorithms. Under ETH, succinct encodings carry $2^{Ω(n)}$ lower bounds. Verification requires $\geq 2^{n-1}$ witness pairs.
Two results carry empirical conditions. Conditional on Landauer's principle ($k_BT\ln 2$ per bit erasure; experimentally confirmed 2012), $dU\geqλ\,dC$ follows by composition with bit-operation bounds; rejecting it requires rejecting Landauer. Conditional on stochastic thermodynamics (Barato--Seifert 2015), $\mathrm{Var}(J)/\langle J\rangle^2\geq 2/σ$ bounds decision precision by entropy production, minimal $σ$ scaling with $\mathrm{srank}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_15571 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Computational Complexity of Physical Counting Simas, Tristan Computational Complexity Logic in Computer Science Mathematical Physics Category Theory 82B35, 20C35, 68Q15, 68Q17, 94A15, 94A17, 03B35, 82B31, 20B30 F.1.3; F.2.2; G.2.1; H.1.1; I.2.3 We characterize which coordinates of a factored state space determine optimal actions. For $\mathcal{D}=(A,S,U)$ with $S=X_1\times\cdots\times X_n$, coordinate set $I$ is sufficient if $s_I=s'_I\Rightarrow\operatorname{Opt}(s)=\operatorname{Opt}(s')$. The decision quotient $Q=S/{\sim}$ ($s\sim s'\Leftrightarrow\operatorname{Opt}(s)=\operatorname{Opt}(s')$) is the minimal abstraction: any abstraction preserving optimal actions factors uniquely through $Q$. We prove fourteen first-principles theorems (thirteen from pure mathematics, one empirical). The chain from counting measure to probability to Bayes' theorem to $Q$ follows from finite set cardinality. Fisher information, entropy, optimal transport, rate-distortion, and thermodynamics each independently recover $\mathrm{srank}$ as decision complexity measure. From $\log x\leq x-1$ alone, Bayesian updating uniquely minimizes expected log loss. Complexity: SUFFICIENCY-CHECK and MINIMUM-SUFFICIENT-SET are coNP-complete; ANCHOR-SUFFICIENCY is $Σ_2^P$-complete; stochastic and sequential variants PP- and PSPACE-complete with strict separation. Six subcases admit polynomial algorithms. Under ETH, succinct encodings carry $2^{Ω(n)}$ lower bounds. Verification requires $\geq 2^{n-1}$ witness pairs. Two results carry empirical conditions. Conditional on Landauer's principle ($k_BT\ln 2$ per bit erasure; experimentally confirmed 2012), $dU\geqλ\,dC$ follows by composition with bit-operation bounds; rejecting it requires rejecting Landauer. Conditional on stochastic thermodynamics (Barato--Seifert 2015), $\mathrm{Var}(J)/\langle J\rangle^2\geq 2/σ$ bounds decision precision by entropy production, minimal $σ$ scaling with $\mathrm{srank}$. |
| title | Computational Complexity of Physical Counting |
| topic | Computational Complexity Logic in Computer Science Mathematical Physics Category Theory 82B35, 20C35, 68Q15, 68Q17, 94A15, 94A17, 03B35, 82B31, 20B30 F.1.3; F.2.2; G.2.1; H.1.1; I.2.3 |
| url | https://arxiv.org/abs/2601.15571 |