
arXiv: 2511.00058
We present a unifying representation of computation as a two-player game between an \emph{Algorithm} and \emph{Nature}, grounded in domain theory and game theory. The Algorithm produces progressively refined approximations within a Scott domain, while Nature assigns penalties proportional to their distance from the true value. Correctness corresponds to equilibrium in the limit of refinement. This framework allows us to define complexity classes game-theoretically, characterizing $\mathbf{P}$, $\mathbf{NP}$, and related classes as sets of problems admitting particular equilibria. The open question $\mathbf{P} \stackrel{?}{=} \mathbf{NP}$ becomes a problem about the equivalence of Nash equilibria under differing informational and temporal constraints.
Computer Science and Game Theory, FOS: Computer and information sciences, Computational Complexity, Logic in Computer Science, 03B70, F.4.1, Computational Complexity (cs.CC), Computer Science and Game Theory (cs.GT), Logic in Computer Science (cs.LO)
Computer Science and Game Theory, FOS: Computer and information sciences, Computational Complexity, Logic in Computer Science, 03B70, F.4.1, Computational Complexity (cs.CC), Computer Science and Game Theory (cs.GT), Logic in Computer Science (cs.LO)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
