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

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

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)

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

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)