How to Submit
Browse
Events
Communities
About

Sparse complete sets for coNP: Solution of the P versus NP problem

18 October 2021, Version 2
Working Paper
This content is an early or alternative research output and has not been peer-reviewed by Cambridge University Press at the time of posting.

Abstract

P versus NP is considered as one of the most important open problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? 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 coNP. Whether NP = coNP is another fundamental question that it is as important as it is unresolved. In 1979, Fortune showed that if any sparse language is coNP-complete, then P = NP. We prove there is a possible sparse language in coNP-complete. In this way, we demonstrate the complexity class P is equal to NP.

Keywords

complexity classes
complement language
sparse
completeness
polynomial time

Supplementary weblinks

Title
Description
Actions
Title
Home Page
Description
Author's home page.
Actions
View

Comments

Comments are not moderated before they are posted, but they can be removed by the site moderators if they are found to be in contravention of our Commenting and Discussion Policy [opens in a new tab] - please read this policy before you post. Comments should be used for scholarly discussion of the content in question. You can find more information about how to use the commenting feature here [opens in a new tab] .
This site is protected by reCAPTCHA and the Google Privacy Policy [opens in a new tab] and Terms of Service [opens in a new tab] apply.

Version History

Oct 18, 2021 Version 2

Version Notes

I detected a flaw in the Theorem 4.10 in the previous version which can be fixed by changing the content of the paper. Note that, it is the same metadata: the title, abstract, classifications and keywords are exactly the same. I only changed the content.

Metrics

878
462
0
Views
Downloads
Citations

License

CC logo
CC
BY logo
BY
The content is available under CC BY 4.0 [opens in a new tab]

DOI

10.33774/coe-2021-m6v73-v2
D O I: 10.33774/coe-2021-m6v73-v2 [opens in a new tab]

Author’s competing interest statement

The author(s) have declared they have no conflict of interest with regard to this content

Ethics

The author(s) have declared ethics committee/IRB approval is not relevant to this content

Share