P=NP in Polylogarithmic Time with Holographic Proofs and Search-to-Decision Reduction

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 the Boolean Satisfiability Problem (SAT) can be solved in $O(\log^2 n)$ time --- which remains polylogarithmic and thus strictly within P --- by combining two fundamental results in computational complexity theory: the PCP Theorem, which establishes that every NP proof can be verified by reading only $O(\log n)$ random bits and a constant number of proof bits (Holographic Proofs), and the Search-to-Decision Reduction, which exploits the self-reducibility of SAT to construct a satisfying assignment using a logarithmic number of decision queries. Since each of the $O(\log n)$ decision queries can be verified in $O(\log n)$ time via the PCP Theorem, the total complexity is $O(\log n) \times O(\log n) = O(\log^2 n)$, which is polylogarithmic. Since SAT is NP-complete, this implies $\mathrm{P}=\mathrm{NP}$.

Fields of Study & Subjects

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

Publication details

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