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

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]