The graph isomorphism problem: its structural complexity

From MaRDI portal





The aim of this book is two-fold: On the one hand, the authors want to give an almost complete overview on interesting developments regarding the complexity of the graph isomorphism problem. But on the other hand they use the opportunity to introduce the reader to the field of structural complexity theory. The light and fluent style, as well as the many well-chosen examples make it a real pleasure to work with this book. The book consists of four chapters: 1) Decision Problems, Search Problems, and Counting Problems, 2) Quantifiers, Games, and Interactive Proofs, 3) Circuits and Sparse Sets, 4) Counting Properties. In my opinion, the first two chapters are the most important ones, which should be interesting and understandable to all readers. Chapters 3) and 4) use advanced methods and constructions, which are suitable for the more interested reader only. In the first chapter first an introduction is given to the central complexity classes \(P\) and \(NP\), as well as to various reducibility notions used throughout the book. Then the authors define the three main types of problems to be considered: Decision problems, where the expected answer to a given input is YES (accept the input) or NO (reject the input); Search problems, where the expected answer to a given input is a SOLUTION (if there is one) or the answer NO (if no solution is possible); Counting problems, where the expected answer to a given input is a natural number, namely the number of different solutions to the problem described by the input. The second chapter introduces the polynomial time hierarchy first. Then the topic of interactive proof systems is treated in detail. Especially, interactive proof systems are given for the graph isomorphism problem itself (which is easy), but also for the complementary problem of graph nonisomorphism. Moreover, a zero-knowledge proof for graph isomorphisms is described. The remainder of this chapter is devoted to the concepts of probabilism and lowness. In the third chapter the class of problems decidable by polynomial size circuits is introduced. This class is equal to the closure of the class of sparse sets under Turing-reduction. The authors prove a consequence of the hypothesis that graph isomorphism have polynomial size circuits, namely then graph isomorphism is low for the class MA. Unfortunately, I cannot estimate how likely or unlikely this consequence is. On the other hand in this chapter it is shown that the presence of a sparse oracle is enough to put graph isomorphism into the class coNP, and thus (since it is certainly in NP) we can conclude that graph isomorphism is not much harder than \(NP \cap \text{NP}\). The final chapter introduces the counitng classes \(\#P\), \(PP\), \(\oplus P\), \(\text{Gap}P\) and others. A lot of interesting relations between these classes are shown, like the result of Toda that the polynomial time hierarchy is contained in \(BP \cdot \oplus P\). To summarize, I think the authors achieve both of the above mentioned aims; they wrote a wonderful book, which is at the same time very readable and extremely informative.




Cited in
(only showing first 100 items - show all)








This page was built for publication: The graph isomorphism problem: its structural complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4273947)