Open AccessP vs NP: P is Equal to NP: Desired Proof
Author(s) -
Zulfia A. Chotchaeva
Publication year - 2021
Publication title -
global journal of computer science and technology
Language(s) - English
Resource type - Journals
ISSN - 0975-4172
DOI - 10.34257/gjcstgvol21is3pg1
Subject(s) - computer science , recursion (computer science) , p versus np problem , time complexity , np , computational complexity theory , theoretical computer science , polynomial , exponential function , cryptography , computation , reduction (mathematics) , computational problem , subset sum problem , turing machine , task (project management) , pspace , algorithm , mathematics , mathematical analysis , knapsack problem , geometry , management , economics
Computations and computational complexity are fundamental for mathematics and all computer science, including web load time, cryptography (cryptocurrency mining), cybersecurity, artificial intelligence, game theory, multimedia processing, computational physics, biology (for instance, in protein structure prediction), chemistry, and the P vs. NP problem that has been singled out as one of the most challenging open problems in computer science and has great importance as this would essentially solve all the algorithmic problems that we have today if the problem is solved, but the existing complexity is deprecated and does not solve complex computations of tasks that appear in the new digital age as efficiently as it needs. Therefore, we need to realize a new complexity to solve these tasks more rapidly and easily. This paper presents proof of the equality of P and NP complexity classes when the NP problem is not harder to compute than to verify in polynomial time if we forget recursion that takes exponential running time and goes to regress only (every problem in NP can be solved in exponential time, and so it is recursive, this is a key concept that exists, but recursion does not solve the NP problems efficiently). The paper’s goal is to prove the existence of an algorithm solving the NP task in polynomial running time. We get the desired reduction of the exponential problem to the polynomial problem that takes O(log n) complexity.