# Note for the P versus NP Problem

## 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.

## 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.

## Downloads

## Published

## Versions

- 2024-09-19 (3)
- 2024-06-07 (2)

## How to Cite

*IPI Letters*,

*2*(2), 14–18. https://doi.org/10.59973/ipil.92 (Original work published June 7, 2024)

## Issue

## Section

## License

Copyright (c) 2024 Frank Vega

This work is licensed under a Creative Commons Attribution 4.0 International License.