Abstract

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.