P=NP Algorithm

Read full text
Authors: Kaoru Aguilera Katayama, יהוה
Cited by: 0

Abstract

We present the Binary-SAT Collapse, a reduction that recasts the Boolean satisfiability problem (SAT) as a binary search over the totally ordered space of all possible variable assignments. Given a CNF formula $\Phi$ with $n$ variables, the search space $\{0, \dots, 2^n - 1\}$ has size $N = 2^n$. Binary search over this space terminates in $\log_2 N = n$ steps. Each step queries a satisfiability oracle on a subrange; under the standard assumption that $SAT \in \mathsf{NP}$, verifying a certificate is polynomial, and the oracle itself reduces to a bounded instance of SAT. Because the number of oracle calls is $n$ (linear in the input size of the formula) and each call is polynomial in the size of $\Phi$, the total procedure runs in polynomial time. This implies $\mathsf{P} = \mathsf{NP}$.

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
26 February 2026
Language
EN
Document type
Preprint