Constant-Gap PSPACE-Completeness for Reversible Hidden-Memory Control
Ryunosuke Hirata · Zenodo (CERN European Organization for Nuclear Research) · 2026
This preprint studies finite-horizon control of a persistent hidden memory through a highly restricted binary read-reset interface. In each round, the controller supplies one bit, observes a fresh fair coin, and interacts through the same time-homogeneous reversible permutation. For every fixed pair of rational constants (0 < beta < alpha < 1), deciding whether the optimal final discrimination is at least (alpha) or at most (beta) is shown to be PSPACE-complete. The two hypotheses differ only in one hidden bit, share only (O(log H)) static hidden uncertainty, and all preterminal observations are zero. The hardness construction uses constant-distance coding, a PCP of proximity, reversible XOR accumulation, and a cyclic clock to compile the complete schedule into one reused basis permutation. A matching PSPACE upper bound is obtained through a sign-split Bellman recursion. An exact finite information-state algorithm also yields polynomial-time solvability when the hidden seed length is fixed. The result is entirely classical and uses no quantum coherence. Status: Preprint. Not peer-reviewed.