Sparse complete sets for coNP: Solution of the P versus NP problem
| Autor: | Frank Vega |
|---|---|
| Přispěvatelé: | Joysonic |
| Rok vydání: | 2021 |
| Předmět: |
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]
Statement (computer science) polynomial time sparse P versus NP problem ACM: F.: Theory of Computation/F.1: COMPUTATION BY ABSTRACT DEVICES/F.1.3: Complexity Measures and Classes/F.1.3.3: Relations among complexity classes complement language complexity classes Combinatorics ACM: F.: Theory of Computation/F.1: COMPUTATION BY ABSTRACT DEVICES/F.1.3: Complexity Measures and Classes/F.1.3.2: Reducibility and completeness completeness Completeness (order theory) Complexity class general_theoretical_computer_science Time complexity Mathematics Sparse language |
| DOI: | 10.5281/zenodo.2582665 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|