The computational complexity of equivalence and isomorphism problems

DOI10.1007/3-540-45303-2MaRDI QIDQ1581496zbMATH OpenOpenAlexFDO

Authors Thomas Thierauf

Publication date 18 October 2000

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-45303-2

zbMATH Keywords

Boolean circuitsBoolean functionsquasi-equivalencevariations of branching programs

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

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.

Recommendations

• On the computational complexity of some classical equivalence relations on boolean functions
• Mathematical Foundations of Computer Science 2003
• scientific article; zbMATH DE number 1161568
• scientific article; zbMATH DE number 477971
• Boolean function complexity. Advances and frontiers.

Cited in

(14)

• On the complexity of polytope isomorphism problems
• On the isomorphism problem for decision trees and decision lists
• The isomorphism conjecture for NP
• Complexity classifications for different equivalence and audit problems for Boolean circuits
• On the Complexity of Matroid Isomorphism Problems
• scientific article; zbMATH DE number 5568412 (Why is no real title available?)
• scientific article; zbMATH DE number 4062853 (Why is no real title available?)
• scientific article; zbMATH DE number 1302479 (Why is no real title available?)
• scientific article; zbMATH DE number 1332670 (Why is no real title available?)
• Measuring the complexity of reductions between equivalence relations
• The Complexity of Order Type Isomorphism
• Mathematical Foundations of Computer Science 2003
• Equilibria problems on games: complexity versus succinctness
• Complexity classes of equivalence problems revisited

This page was built for publication: The computational complexity of equivalence and isomorphism problems

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