The Graph Isomorphism problem is one of the few problems in the class NP that is not known to be complete nor polynomial time solvable. Because of its theoretical and practical importance the problem has been studied from many different approaches.
This tutorial will present several results that provide a better understanding of the relative position of the Graph Isomorphism problem in NP and other complexity classes. The GI problem will be used to illustrate important concepts in Complexity Theory like reducibilities, interactive proofs, counting properties, enumeration of the solutions or circuit complexity.