Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ ZENODOarrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
ZENODO
Preprint
Data sources: ZENODO
addClaim

P=NP in O(1) Time via Infinite Holography

Authors: Aguilera Katayama, Kaoru;

P=NP in O(1) Time via Infinite Holography

Abstract

We present an argument that the Boolean Satisfiability Problem (SAT) 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. Whereas Meta-Holography applies finitely many layers of holographic compression --- reducing $O(\log^2 n)$ to $O(\log \ log\ n)$ to $O(\log \ log \ log \ n)$ and so on --- Infinite Holography takes this process to its limit, producing a fixed-point proof structure in which the entire computational content of SAT is pre-encoded into a static holographic object. This object functions as an oracle: given any SAT instance, the answer is accessible in $O(1)$ time by reading a constant number of bits from the structure. Since the Infinite Holographic Structure is the limit of infinitely many valid applications of the PCP Theorem, each layer sound with probability $1 - \epsilon$, and since this limit converges, the structure is well-defined and sound. Because SAT is NP-complete, this implies $\mathrm{P} = \mathrm{NP}$.

Powered by OpenAIRE graph
Found an issue? Give us feedback