Download PDFOpen PDF in browserCurrent versionP versus NPEasyChair Preprint no. 3061, version 29 pages•Date: April 4, 2020AbstractP 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? 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 classes are L and NL. Whether L = NL is another fundamental question that it is as important as it is unresolved. We demonstrate that every problem in NP could be NLreduced to another problem in L. In this way, we prove that every problem in NP is in NL with L Oracle. Moreover, we show the complexity class NP is equal to NL, since it is wellknown that the logarithmic space oracle hierarchy collapses into NL. Keyphrases: completeness, complexity classes, logarithmic space, oneway, polynomial time, reduction
