Downloads provided by UsageCounts
doi: 10.20944/preprints201908.0037.v1 , 10.5281/zenodo.3551006 , 10.5281/zenodo.3364026 , 10.5281/zenodo.3366349 , 10.5281/zenodo.3357245 , 10.5281/zenodo.3355813 , 10.5281/zenodo.3539702 , 10.5281/zenodo.3357974 , 10.5281/zenodo.3355777 , 10.5281/zenodo.3534294 , 10.6084/m9.figshare.10309058 , 10.6084/m9.figshare.10309058.v1
doi: 10.20944/preprints201908.0037.v1 , 10.5281/zenodo.3551006 , 10.5281/zenodo.3364026 , 10.5281/zenodo.3366349 , 10.5281/zenodo.3357245 , 10.5281/zenodo.3355813 , 10.5281/zenodo.3539702 , 10.5281/zenodo.3357974 , 10.5281/zenodo.3355777 , 10.5281/zenodo.3534294 , 10.6084/m9.figshare.10309058 , 10.6084/m9.figshare.10309058.v1
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 f ailed. NP is the complexity class of languages defined b y p olynomial t ime v erifiers M su ch th at wh en th e in put is an el ement of the language with its certificate, then M outputs a string which belongs to a single language in P. Another major complexity classes are L and NL. The certificate-based definition of NL is based on logarithmic space Turing machine with an additional special read-once input tape: This is called a logarithmic space verifier. NL is the complexity class of languages defined by logarithmic space verifiers M s uch t hat when t he i nput i s a n e lement o f t he l anguage with i ts c ertificate, th en M outputs 1. To attack the P versus NP problem, the NP-completeness is a useful concept. We demonstrate there is an NP-complete language defined by a logarithmic space verifier M such that when the input is an element of the language with its certificate, then M outputs a s tring which belongs to a single language in L. In this way, we obtain if L is not equal to NL, then P = NP. In addition, we show that L is not equal to NL. Hence, we prove the complexity class P is equal to NP.
Completeness, polynomial time, reduction, Complexity classes, verifier, complexity classes, Verifier, completeness, Polynomial time, Logarithmic space, general_theoretical_computer_science, logarithmic space, Reduction
Completeness, polynomial time, reduction, Complexity classes, verifier, complexity classes, Verifier, completeness, Polynomial time, Logarithmic space, general_theoretical_computer_science, logarithmic space, Reduction
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
| views | 18 | |
| downloads | 29 |

Views provided by UsageCounts
Downloads provided by UsageCounts