Saved in:
| Main Author: | |
|---|---|
| Format: | Recurso digital |
| Language: | |
| Published: |
Zenodo
2026
|
| Online Access: | https://doi.org/10.5281/zenodo.19157220 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of 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>