Note for the P versus NP Problem

We improved the Lemma 1 according to the comments of the reviewer Sergi Simon. Besides, we added a Discussion section where we contributed and included important remarks to the final result. In addition, we picked up the discipline of "Data structures and Algorithms" since it is very close to the scope of the paper as well.

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): 28 March 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.v2

SO-VID: 5e6e97ed-697f-4685-a43b-6c48e598af02

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

Frank Vega wrote:

With the help of the reviewer Sergi Simon, we detected a minor detail in this last version. However, that issue was a very simple and small mistake that I commited when I was writing the paper and so, it does not deserve a third version. I fixed and replaced the following statement in latex (over the definition of the K-CLOSURE problem):

--------------------------------

Note that in this problem the statement ``either $u \in V'$ or $v \notin V'$'' does mean the same as ($u \in V'$ or $v \in V'$) or ($u \notin V'$ or $v \notin V'$) since the logical implication of the word ``\textbf{Either}'' indicates that at least one of the following statements must be true, but not necessarily both.

-------------------------------

by the correct one:

------------------------------

Note that in this problem the phrase ``either $u \in V'$ or $v \notin V'$'' does mean the same as ($u \in V'$ and $v \in V'$) or ($u \notin V'$ and $v \notin V'$) since the logical implication of the words ``\textbf{either ... or ...}'' indicates that exactly one of the following statements can be true.

------------------------------

As you can see it is only one sentence, but the paper would be perfect after that. You may check this change in the following preprint:

https://www.techrxiv.org/users/258307/articles/716221-note-for-the-p-versus-np-problem

I hope this can be taken into account by the readers for their final moment of evaluating this version,

2024-04-18 19:39 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]