P ¹ NP: A Formal Proof
Downloads
According to the conjecture that P ¹ NP, we recall in this paper that class NP includes P, NP-intermediate and NP-complete problems (some of Co-NP and NP-hard problems also belong to NP). It is obvious that if a single problem belonging to NP is formally proved non-polynomial, then P ¹ NP no longer remains a conjecture but rather becomes a formal statement. In this purpose, we formally prove that the Graph-isomorphism problem (belonging to class NP) is non-polynomial time, which leads that P ¹ NP is a formal statement, not a conjecture.
Mahdoum "CAD of Circuits and Integrated Systems" Wiley (1st ed.), October 2020, Hoboken, USA.
M.R. Garey, D.S. Johnson "Computers and Intractability: a Guide to the Theory of NP-Completeness" Freeman (1st ed.), 1979, San Fransisco, USA.
Mahdoum "Book review: Representations for genetic and evolutionary algorithms, written by F. Rothlauf" J. The Computer 49, 5 (September 2006).
Copyright (c) 2024 International Journal of Emerging Trends in Science and Technology
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
