Thierauf, Thomas The computational complexity of equivalence and isomorphism problems. (English) Zbl 0966.68083 Lecture Notes in Computer Science. 1852. Berlin: Springer. viii, 135 p. (2000). 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. Reviewer: U.Schöning (Ulm) Cited in 2 Documents MSC: 68Q25 Analysis of algorithms and problem complexity 68-02 Research exposition (monographs, survey articles) pertaining to computer science 05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) 68W20 Randomized algorithms Keywords:quasi-equivalence; Boolean circuits; variations of branching programs; Boolean functions PDFBibTeX XMLCite \textit{T. Thierauf}, The computational complexity of equivalence and isomorphism problems. Berlin: Springer (2000; Zbl 0966.68083) Full Text: DOI