Computational Complexity and Graph Isomorphism
Laulumaa, Joonas (2015)
2015
Tietotekniikan koulutusohjelma
Tieto- ja sähkötekniikan tiedekunta - Faculty of Computing and Electrical Engineering
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2015-02-04
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tty-201501291040
https://urn.fi/URN:NBN:fi:tty-201501291040
Tiivistelmä
The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic, that is, structurally the same. The complexity of graph isomorphism is an open problem and it is one of the few problems in NP which is neither known to be solvable in polynomial time nor NP-complete. It is one of the most researched open problems in theoretical computer science.
The foundations of computability theory are in recursion theory and in recursive functions which are an older model of computation than Turing machines. In this master’s thesis we discuss the basics of the recursion theory and the main theorems starting from the axioms. The aim of the second chapter is to define the most important T- and m-reductions and the implication hierarchy between reductions.
Different variations of Turing machines include the nondeterministic and oracle Turing machines. They are discussed in the third chapter. A hierarchy of different complexity classes can be created by reducing the available computational resources of recursive functions. The members of this hierarchy include for instance P and NP. There are hundreds of known complexity classes and in this work the most important ones regarding graph isomorphism are introduced.
Boolean circuits are a different method for approaching computability. Some main results and complexity classes of circuit complexity are discussed in the fourth chapter. The aim is to show that graph isomorphism is hard for the class DET.
Graph isomorphism is known to belong to the classes coAM and SPP. These classes are introduced in the fifth chapter by using theory of probabilistic classes, polynomial hierarchy, interactive proof systems and Arthur-Merlin games. Polynomial hierarchy collapses to its second level if GI is NP-complete.
The foundations of computability theory are in recursion theory and in recursive functions which are an older model of computation than Turing machines. In this master’s thesis we discuss the basics of the recursion theory and the main theorems starting from the axioms. The aim of the second chapter is to define the most important T- and m-reductions and the implication hierarchy between reductions.
Different variations of Turing machines include the nondeterministic and oracle Turing machines. They are discussed in the third chapter. A hierarchy of different complexity classes can be created by reducing the available computational resources of recursive functions. The members of this hierarchy include for instance P and NP. There are hundreds of known complexity classes and in this work the most important ones regarding graph isomorphism are introduced.
Boolean circuits are a different method for approaching computability. Some main results and complexity classes of circuit complexity are discussed in the fourth chapter. The aim is to show that graph isomorphism is hard for the class DET.
Graph isomorphism is known to belong to the classes coAM and SPP. These classes are introduced in the fifth chapter by using theory of probabilistic classes, polynomial hierarchy, interactive proof systems and Arthur-Merlin games. Polynomial hierarchy collapses to its second level if GI is NP-complete.