| _version_ | 1866901866495868928 |
|---|---|
| author | Aguilera Katayama, Kaoru |
| author_facet | Aguilera Katayama, Kaoru |
| contents | <p>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.</p> |
| format | Recurso digital |
| id | zenodo_https___doi_org_10_5281_zenodo_19157220 |
| institution | Zenodo |
| language | |
| publishDate | 2026 |
| publisher | Zenodo |
| record_format | zenodo |
| spellingShingle | P = NP via Constructive Bidirectional Polynomial-Time Reduction Between SAT and Binary Search Aguilera Katayama, Kaoru <p>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.</p> |
| title | P = NP via Constructive Bidirectional Polynomial-Time Reduction Between SAT and Binary Search |
| url | https://doi.org/10.5281/zenodo.19157220 |