P=NP in Polylogarithmic Time with Holographic Proofs and Search-to-Decision Reduction
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