Formal Complexity Classes for Time Travel Computation

Closed timelike curves (CTCs) and retrocausal models challenge conventional notions of computation by permitting interactions with an agent’s own causal past. Prior work by Deutsch, Aaronson, and Watrous has shown that access to CTCs augments classical and quantum computational power, collapsing complexity classes in surprising ways. In this paper, we propose a formal hierarchy of complexity classes for time-travel computation, introducing CTC-PTIME, CTC-NP, and their quantum analogues. We provide rigorous definitions using retrocausal oracle access and fixed-point operators, prove containments and separations, and situate these classes relative to P, NP, PSPACE, and BQP. We also present new paradox-aware reductions, illustrate paradox resolution as a computational primitive, and propose open problems at the interface of causality, complexity, and temporal logic.