Computation as a Game
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915589312741376 |
|---|---|
| author | Bilokon, Paul Alexander |
| author_facet | Bilokon, Paul Alexander |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_00058 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Computation as a Game Bilokon, Paul Alexander Computational Complexity Computer Science and Game Theory Logic in Computer Science 03B70 F.4.1 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. |
| title | Computation as a Game |
| topic | Computational Complexity Computer Science and Game Theory Logic in Computer Science 03B70 F.4.1 |
| url | https://arxiv.org/abs/2511.00058 |