P vs NP: P is Equal to NP: Desired Proof

α
Zulfia A. Chotchaeva
Zulfia A. Chotchaeva
α Lomonosov Moscow State University Lomonosov Moscow State University

Send Message

To: Author

P vs NP: P is Equal to NP: Desired Proof

Article Fingerprint

ReserarchID

OVQ36

P vs NP: P is Equal to NP: Desired Proof Banner

AI TAKEAWAY

Connecting with the Eternal Ground
  • English
  • Afrikaans
  • Albanian
  • Amharic
  • Arabic
  • Armenian
  • Azerbaijani
  • Basque
  • Belarusian
  • Bengali
  • Bosnian
  • Bulgarian
  • Catalan
  • Cebuano
  • Chichewa
  • Chinese (Simplified)
  • Chinese (Traditional)
  • Corsican
  • Croatian
  • Czech
  • Danish
  • Dutch
  • Esperanto
  • Estonian
  • Filipino
  • Finnish
  • French
  • Frisian
  • Galician
  • Georgian
  • German
  • Greek
  • Gujarati
  • Haitian Creole
  • Hausa
  • Hawaiian
  • Hebrew
  • Hindi
  • Hmong
  • Hungarian
  • Icelandic
  • Igbo
  • Indonesian
  • Irish
  • Italian
  • Japanese
  • Javanese
  • Kannada
  • Kazakh
  • Khmer
  • Korean
  • Kurdish (Kurmanji)
  • Kyrgyz
  • Lao
  • Latin
  • Latvian
  • Lithuanian
  • Luxembourgish
  • Macedonian
  • Malagasy
  • Malay
  • Malayalam
  • Maltese
  • Maori
  • Marathi
  • Mongolian
  • Myanmar (Burmese)
  • Nepali
  • Norwegian
  • Pashto
  • Persian
  • Polish
  • Portuguese
  • Punjabi
  • Romanian
  • Russian
  • Samoan
  • Scots Gaelic
  • Serbian
  • Sesotho
  • Shona
  • Sindhi
  • Sinhala
  • Slovak
  • Slovenian
  • Somali
  • Spanish
  • Sundanese
  • Swahili
  • Swedish
  • Tajik
  • Tamil
  • Telugu
  • Thai
  • Turkish
  • Ukrainian
  • Urdu
  • Uzbek
  • Vietnamese
  • Welsh
  • Xhosa
  • Yiddish
  • Yoruba
  • Zulu

Abstract

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.

References

30 Cites in Article
  1. Scott Aaronson (2017). $$P\mathop{ =}\limits^{?}NP$$.
  2. M Agrawal,E Allender,R Impagliazzo,T Pitassi,S Rudich (2001). Reducing the complexity of reductions.
  3. S Arora,B Barak (2009). Computational complexity: a modern approach.
  4. G Boolos,J Burgess,R Jeffrey (2007). Computability and logic.
  5. A Cobham (1965). The intrinsic computational difficulty of functions.
  6. I Cormen,C Leiserson,R Rivast,C Stein (2009). Introduction to algorithms.
  7. Stephen Cook (1971). The complexity of theorem-proving procedures.
  8. S Cook (2000). Hodges Conjecture Clay Institute Millennium Problem Solution.
  9. S Cooper (1994). Computability theory.
  10. Z Chotchaeva (2020). The new matrix model of computation based purely on quite a new concept of the matrix computations for extremely quick web pages loading.
  11. Martin Davis,Hilary Putnam (1959). A Computing Procedure for Quantification Theory.
  12. Martin Davis,George Logemann,Donald Loveland (1961). A machine program for theorem-proving.
  13. Lance Fortnow (2009). The status of the P versus NP problem.
  14. M Garey,O Johnson (1979). Computers and Intractability.
  15. William Gasarch (2002). Hilbert's Tenth Problem.
  16. K Gȍdel (1931). Kurt Gödel: On Formally Undecidable Propositions of Principia Mathematica and Related Systems I (1931).
  17. Oded Goldreich,Np (2010). P, NP, and NP-Completeness.
  18. Juris Hartmanis (1989). Gödel, von Neumann and the P =? NP Problem.
  19. D Hilbert (2000). Mathematical problems.
  20. John Hopcroft,Rajeev Motwani,Jeffrey Ullman (2001). Introduction to automata theory, languages, and computation, 2nd edition.
  21. Richard Karp (1972). Reducibility Among Combinatorial Problems.
  22. J Kleinberg,E Tardos (2005). Algorithm design.
  23. Richard Ladner (1975). On the Structure of Polynomial Time Reducibility.
  24. R Lipton,R M Karp (1980). Some connections between nonuniform complexity classes.
  25. Morten Heine,B Sorensen,Pawel Urzyczyn (1998). The Curry-Howard isomorphism.
  26. Von Neumann (2005). Letters to F.B. Silsbee.
  27. C Papadimitriou (1993). Computational Complexity.
  28. M Sipser (2012). Introduction to the Theory of Computation.
  29. Steve Smale (2000). Mathematical problems for the next century.
  30. Jackie Koerner (2021). Wikipedia Has a Bias Problem.

Funding

No external funding was declared for this work.

Conflict of Interest

The authors declare no conflict of interest.

Ethical Approval

No ethics committee approval was required for this article type.

Data Availability

Not applicable for this article.

How to Cite This Article

Zulfia A. Chotchaeva. 2021. \u201cP vs NP: P is Equal to NP: Desired Proof\u201d. Global Journal of Computer Science and Technology - G: Interdisciplinary GJCST-G Volume 21 (GJCST Volume 21 Issue G3): .

Download Citation

An academic article on the importance of P vs. NP problem in computer science research. Highlighting its significance in computational complexity theory.
Journal Specifications

Crossref Journal DOI 10.17406/gjcst

Print ISSN 0975-4350

e-ISSN 0975-4172

Keywords
Classification
GJCST-G Classification: I.2.8
Version of record

v1.2

Issue date

September 12, 2021

Language
en
Experiance in AR

Explore published articles in an immersive Augmented Reality environment. Our platform converts research papers into interactive 3D books, allowing readers to view and interact with content using AR and VR compatible devices.

Read in 3D

Your published article is automatically converted into a realistic 3D book. Flip through pages and read research papers in a more engaging and interactive format.

Article Matrices
Total Views: 3593
Total Downloads: 915
2026 Trends
Related Research

Published Article

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.

Our website is actively being updated, and changes may occur frequently. Please clear your browser cache if needed. For feedback or error reporting, please email [email protected]

Request Access

Please fill out the form below to request access to this research paper. Your request will be reviewed by the editorial or author team.
X

Quote and Order Details

Contact Person

Invoice Address

Notes or Comments

This is the heading

Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut elit tellus, luctus nec ullamcorper mattis, pulvinar dapibus leo.

High-quality academic research articles on global topics and journals.

P vs NP: P is Equal to NP: Desired Proof

Zulfia A. Chotchaeva
Zulfia A. Chotchaeva Lomonosov Moscow State University

Research Journals