Note for the P versus NP Problem (II)

01 July 2024, Version 3
This content is an early or alternative research output and has not been peer-reviewed by Cambridge University Press at the time of posting.

Abstract

One of the biggest unsolved mysteries in computer science is the P versus NP problem. It asks a simple question: can every problem whose solution can be quickly verified be solved just as quickly (Here, "quickly" means in polynomial time)? While the question itself was hinted at in a 1955 letter from John Nash, a formalization of the problem is credited to Stephen Cook and Leonid Levin. Despite decades of effort, no one has been able to definitively answer it. Closely related is the concept of NP-completeness. If even one NP-complete problem can be solved efficiently (in polynomial time), then it implies P equals NP. This work proposes that a specific NP-complete problem, ONE-IN-THREE 3SAT, can be solved efficiently. In this way, we prove that P is equal to NP.

Keywords

Complexity classes
Boolean formula
Graph
Completeness
Polynomial time

Comments

Comments are not moderated before they are posted, but they can be removed by the site moderators if they are found to be in contravention of our Commenting and Discussion Policy [opens in a new tab] - please read this policy before you post. Comments should be used for scholarly discussion of the content in question. You can find more information about how to use the commenting feature here [opens in a new tab] .
This site is protected by reCAPTCHA and the Google Privacy Policy [opens in a new tab] and Terms of Service [opens in a new tab] apply.