PulseExploreJournal ClubDebatesTrendingResearchersJournals
Instagram
HomeExploreJournal ClubTrending
Synapse
⌘+K
Synapse
April 22, 20240 citationsOpen Access

Note for the P versus NP Problem

View Full Paper
FVFrank Vega

Key Points

Key points are not available for this paper at 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.

Ask AI
Helpful
Bookmark
Share
View Full Paper

Cite This Study

Frank Vega (2024) studied this question.

synapsesocial.com/papers/68e6e2e0b6db64358765e44ahttps://doi.org/10.33774/coe-2024-pmlqm-v9
Ask AI
Helpful
Bookmark
Share
View Full Paper