The computational complexity of equivalence and isomorphism problems (Q1581496)

The book undertakes a systematic study of equivalence problems and ``quasi-equivalence'' problems among different algorithmic computation models. The computation models studied in this book are Boolean circuits and variations of branching programs, both of which are used to represent Boolean functions. Under ``quasi-equivalence'' problems we understand certain isomorphism and congruence problems. The methods used are randomization, approximate counting, almost uniform random number generation, arithmetization and interactive proof protocols. The relationship to more standard combinatorial problems, like satisfiability, clique, and graph isomorphism is also studied. This is a well-written, self-contained, nice monograph which is very much suited for self-study, or as a basis for a graduate-level seminar or thesis.