The theory of classifying problems based on how difficult they are to solve. A problem is assigned to the P-problem (polynomial-time) class
if the number of steps needed to solve it is bounded by some power
of the problem's size. A problem is assigned to the NP-problem
(nondeterministic polynomial-time) class if it permits a nondeterministic solution
and the number of steps to verify the solution is bounded by some power of the problem's
size. The class of P-problems is a subset of the class
of NP-problems, but there also exist problems which
are not NP.
There exists no known P algorithm for graph isomorphism testing, although the problem has also not been shown to be NP-complete.
In fact, the problem of identifying isomorphic graphs
seems to fall in a crack between P and NP-complete, if such a crack exists (Skiena
1990, p. 181), and as a result, the problem is sometimes assigned to a special
graph isomorphism complete complexity
class.
