Note for the P versus NP Problem

Sergi Simon detected an error in a single sentence related to the definition of the K-CLOSURE problem. We think this current version is good enough this time.

Abstract

P versus NP is considered as one of the most fundamental open problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? It was essentially mentioned in 1955 from a letter written by John Nash to the United States National Security Agency. However, a precise statement of the P versus NP problem was introduced independently by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this problem have failed. Another major complexity class is NP-complete. It is well-known that P is equal to NP under the assumption of the existence of a polynomial time algorithm for some NP-complete. We show that the Monotone Weighted Xor 2-satisfiability problem (MWX2SAT) is NP-complete and P at the same time. Certainly, we make a polynomial time reduction from every directed graph and positive integer k in the K-CLOSURE problem to an instance of MWX2SAT. In this way, we show that MWX2SAT is also an NP-complete problem. Moreover, we create and implement a polynomial time algorithm which decides the instances of MWX2SAT. Consequently, we prove that P = NP.

Content

Author and article information

Journal

Title: ScienceOpen Preprints

Publisher: ScienceOpen

Publication date (Electronic preprint): 20 April 2024

Affiliations

[1 ] GROUPS PLUS TOURS INC., 9611 Fontainebleau Blvd, Miami, FL, 33172, USA;

Author notes

[* ]Email: vega.frank@ 123456gmail.com .

Author information

Frank Vega https://orcid.org/0000-0001-8210-4126

Article

DOI: 10.14293/PR2199.000759.v3

SO-VID: d6a6122f-1ee6-4421-854c-7ac36cacb691

License:

This work has been published open access under Creative Commons Attribution License CC BY 4.0 , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Conditions, terms of use and publishing policy can be found at www.scienceopen.com .

History

Date received : 15 March 2024

References

Fortnow Lance. The status of the P versus NP problem. Communications of the ACM. Vol. 52(9):78–86. 2009. Association for Computing Machinery (ACM). [Cross Ref]

Comments

Eric Brandwein wrote:

Re-commenting on the latest version:

Sorry to burst your bubble, but the book you cite is incorrect. Notice that the only source for the claim that K-CLOSURE is NP-complete is a never published private communication. In fact, if K-CLOSURE was actually NP-complete, there would be a much shorter proof that P = NP; just take the empty set of vertices as a solution! If the problem is instead about a non-empty subset of vertices (which the statement doesn't clarify), then it is the same problem as finding the smallest weakly connected component of the directed graph, which would also be a shorter proof.

Amazingly, your thought process seems to be correct, although very informally written. I would recommend reading other math papers and consulting peers to get the right tone. Keep at it!

2025-03-27 14:54 UTC

Comment on this article

[1] Fortnow Lance. The status of the P versus NP problem. Communications of the ACM. Vol. 52(9):78–86. 2009. Association for Computing Machinery (ACM). [Cross Ref]

One-Click Submission System Now Available for SO Preprints, learn more on how this works in our blog post and don't forget to check the video, too!