P = NP via Constructive Bidirectional Polynomial-Time Reduction Between SAT and Binary Search

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 a constructive proof that P = NP. The argument proceeds by establishing an explicit, polynomial-time bidirectional reduction between the Boolean Satisfiability Problem (SAT)-the canonical NP-complete problem-and Binary Search on a sorted array-a problem solvable in O(log n) time, trivially in P. We construct, for any CNF formula φ with n variables and m clauses, a sorted array A φ of size O(m + n) and a target value τ φ such that φ is satisfiable if and only if τ φ is found in A φ via binary search, and the satisfying assignment is extractable from the search result. Since binary search runs in O(log(m + n)) time and the reduction is polynomial, SAT is decided in polynomial time. As SAT is NP-complete, every problem in NP is thereby solvable in polynomial time, establishing P = NP. We provide complete constructions, formal correctness proofs, complexity analyses, and a worked numerical example.

Fields of Study & Subjects

Complexity and Algorithms in Graphs Advanced Graph Theory Research Constraint Satisfaction and Optimization

Publication details

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