P versus NP

EasyChair Preprint no. 3061, version history

VersionDatePagesVersion notes
1March 29, 20208
2April 4, 20209

Maybe, it was not clear enough the outstanding result that implies the first version. The original submission claims that every problem in NP could be NL-reduced to another problem in L. However, this might be not explicit at all. Indeed, that result implies that every problem in NP is in NL with L Oracle. Neil Immerman proved that NL = coNL. His result provides a direct proof and improvement of the main result in (Buss, Samuel R and Cook, Stephen A and Dymond, Patrick W and Hay, Louise with paper: The Log Space Oracle Hierarchy Collapses), by collapsing the log space oracle hierarchy into NL. In this way, we have that the complexity class NP is equal to NL. This new revision makes more evident this result.

3April 15, 20208

The content was simplified. In this way, the abstract and content of the paper were changed and improved.

4April 23, 20208

This paper is a breakthrough in computer science and mathematics. Indeed, this is a solution for the well-known problem P vs NP. Moreover, using the knowledge introduced in this version with the another paper [1], then it is possible to find a practical and feasible algorithm for the NP-complete problems. It has been discussed that a P = NP solution might be useful for the cure of cancer. For that reason, it is very important this version may be visible in a public site, since this result could be used for worldwide battle that we are engage for the cure of coronavirus. The abstract and content of the paper were changed and improved.

[1] Samuel R. Buss, Stephen A. Cook, Patrick W. Dymond, and Louise Hay. The Log Space Oracle Hierarchy Collapses, July 1987. In Citeseer at http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=C115F3BE20DF7E237DF40CB849AEF37C?doi=10.1.1.5.760&rep=rep1&type=pdf.

5April 25, 20208

Unfortunately, we introduced a flaw in the last version with the counting of the number of clauses from the Boolean formula. Certainly, if we initially count the number of clauses, then the logarithmic space verifier will not be in one-way. However, this is not a fatal error, since this could be fixed adding the number of clauses as a part of the input and checking at the end the number of clauses. This was what we changed in the content of this version.

6April 26, 20208

We forgot to verify in the Algorithm 1 whether K < m or not. We added this new verification in this version.

7June 24, 202014

We create a new version with new content and abstract, but the conclusion is the same result.

8June 29, 202014

We update the abstract and content of the paper, but the result is still the same.

9July 10, 202013

We update the abstract, keywords and content of the paper, but the result is still the same.

10July 11, 202013

We update content and abstract.

11July 18, 202013

We improve the definitions and theory with this version.

12July 20, 202014

I improved the last theorem with the concluded result.

13September 19, 202013

We improve the paper: abstract, keywords and content were changed.

14October 3, 202013

Minor details: we changed abstract and content.

15October 4, 202014

We remove a citation from the abstract and add the Conclusion section.

16October 6, 202014

Minor changes: abstract and content were changed.

17December 7, 202014

Included the Acknowledgments section.

18December 28, 202014

Improved theorem 12.

Keyphrases: completeness, complexity classes, logarithmic space, one-way, polynomial time, reduction

BibTeX entry
BibTeX does not have the right entry for preprints. This is a hack for producing the correct reference:
@Booklet{EasyChair:3061,
  author = {Frank Vega},
  title = {P versus NP},
  howpublished = {EasyChair Preprint no. 3061},

  year = {EasyChair, 2020}}