NP on Logarithmic Space

16 November 2023, Version 6
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$? 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 prove that $NP \subseteq NSPACE(\log^{2} n)$ just using logarithmic space reductions.

Keywords

Complexity Classes
Completeness
Polynomial Time
Reduction
Logarithmic Space
Computational Algorithm

Supplementary weblinks

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.