Since being introduced, the concept of P and NP complexity classes of algorithms have been the main focus in complexity theory. Despite decades of efforts, it remains an open problem whether P = NP. However, most professionals hold the belief that the two classes differ. In this paper, discussion of these two categories of problems will occur, assuming \(P \neq NP\). Work of Richard Ladner that shows the existence of NP intermediate classes of problems given \(P \neq NP\) will be discussed.

The graph isomorphism problem, a commonly believed member of the intermediate class, and the subgraph isomorphism problem will be discussed, primarily based on a type of algorithm for them. Finally, a brief discussion of polynomial hierarchy will be introduced, based on the discussion of these isomorphism problems.

Zoom link