Note for the P Versus NP Problem (II)

EasyChair Preprint 13469, version 6

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.

Keyphrases: Boolean formula, completeness, complexity classes, graph, polynomial time

@booklet{EasyChair:13469,
  author    = {Frank Vega},
  title     = {Note for the P Versus NP Problem (II)},
  howpublished = {EasyChair Preprint 13469},
  year      = {EasyChair, 2024}}