Note for the P versus NP Problem

Frank Vega

doi:10.59973/ipil.92

Authors

Frank Vega Independent Researcher, Cotorro, Havana, Cuba https://orcid.org/0000-0001-8210-4126

DOI:

https://doi.org/10.59973/ipil.92

Keywords:

Complexity classes, Boolean formula, Graph, Completeness, Polynomial 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.

Author Biography

Frank Vega, Independent Researcher, Cotorro, Havana, Cuba

Frank Vega is essentially a Back-End Programmer and Mathematical Hobbyist who graduated in Computer Science in 2007. In May 2022, The Ramanujan Journal accepted his math article about the Riemann hypothesis. The article "Robin's criterion on divisibility" makes several significant contributions to the field of number theory. It provides a proof of the Robin inequality for a large class of integers, and it suggests new directions for research in the area of analytic number theory.

References

Stephen Arthur Cook. The P versus NP Problem, Clay Mathematics Institute.https://www.claymath.org/wp-content/uploads/2022/06/pvsnp.pdf, June 2022. Accessed 25 May 2024.

Lance Fortnow. The status of the P versus NP problem. Communications of the ACM, 52(9):78–86,2009. doi:10.1145/1562164.1562186.

Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to Algorithms. The MIT Press, 3rd edition, 2009.

Michael R Garey and David S Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W. H. Freeman and Company, 1 edition, 1979.

Frank Vega. ALMA—MWX2SAT Solver. https://github.com/frankvegadelgado/alma, February 2024. Accessed 25 May 2024.