$O(1) = \mathrm{R}$: Every Decidable Problem is Solvable in Constant Time via Infinite Holography

Read full text Summarise with VIRAT
Authors: Kaoru Aguilera Katayama
Cited by: 0

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

We present an argument that every decidable (recursive) problem can be solved in $O(1)$ time by introducing the concept of Infinite Holography: the limit structure obtained by applying the PCP Theorem (Holographic Proofs) to its own verification procedure infinitely many times. The key observation is that the PCP Theorem applies not only to NP, but to the verification of any computation whose correctness is expressible as an NP statement --- and the correctness of any decidable computation on a given input is precisely such a statement. Therefore, for any language $L \in \mathrm{R}$ (the class of recursive/decidable languages) and any input $x$, the statement ``the Turing machine $M$ that decides $L$ accepts/rejects $x$'' admits a holographic proof. By applying Infinite Holography --- the process of iterating the PCP Theorem on its own verification procedure ad infinitum --- we obtain an Infinite Holographic Structure (IHS) that encodes the answer to any query about $L$ and is accessible in $O(1)$ time. Since this applies to every decidable language, we conclude $\mathrm{DTIME}(O(1)) = \mathrm{R}$, that is, $O(1) = \mathrm{R}$.

Fields of Study & Subjects

Complexity and Algorithms in Graphs Computability Logic AI Algorithms Advanced Graph Theory Research

Publication details

Journal / source
Zenodo (CERN European Organization for Nuclear Research)
Publication date
1 April 2026
Language
EN
Document type
Preprint