I’m an undergrad student in Computer Science and I’ve been working on a new theoretical model — the Perfect Concurrency (PC) model — that tries to approach the P vs NP problem from a new angle.
The model assumes infinite parallelism and zero overhead, isolating only the total amount of “logical work” an algorithm must perform. Even in this idealized setting, I prove that for all sufficiently large n, any correct algorithm solving SAT must perform Ω(2ⁿ) total work. Then, using a simulation lemma, I show that this lower bound implies SAT ∉ P, and therefore P ≠ NP.
The argument avoids known barriers like relativization, natural proofs, and algebrization. It’s formal, self-contained, and includes two appendices: one for cross-validation against known results, and one FAQ addressing common objections.
Dor_Elbaz|10 months ago
The model assumes infinite parallelism and zero overhead, isolating only the total amount of “logical work” an algorithm must perform. Even in this idealized setting, I prove that for all sufficiently large n, any correct algorithm solving SAT must perform Ω(2ⁿ) total work. Then, using a simulation lemma, I show that this lower bound implies SAT ∉ P, and therefore P ≠ NP.
The argument avoids known barriers like relativization, natural proofs, and algebrization. It’s formal, self-contained, and includes two appendices: one for cross-validation against known results, and one FAQ addressing common objections.
Here is Version 3 of the paper, incorporating all revisions and reviewer feedback so far: https://zenodo.org/records/15263845
I’d be thrilled to hear what you think — and grateful for any feedback, critiques, or questions.
— Dor Elbaz
mika6996|10 months ago