×

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)

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
PDFBibTeX XMLCite
Full Text: DOI