The computational complexity of equivalence and isomorphism problems
type: Item
instance of: scholarly article
title: The computational complexity of equivalence and isomorphism problems
zbMATH Open document ID: 0966.68083
DOI: 10.1007/3-540-45303-2
author: Thomas Thierauf
published in: Lecture Notes in Computer Science
publication date: 2000-10-18T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68-02
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 68W20
zbMATH DE Number: 1519390
zbMATH Keywords: quasi-equivalence
zbMATH Keywords: Boolean circuits
zbMATH Keywords: variations of branching programs
zbMATH Keywords: Boolean functions
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1007/3-540-45303-2
OpenAlex ID: W1517154004
description: scientific article; zbMATH DE number 1519390