文章基本信息

标题：Complexity classifications for different equivalence and audit problems for Boolean circuits
本地全文：下载
作者：Elmar Böhler ; Nadia Creignou ; Matthias Galota 等
期刊名称：Logical Methods in Computer Science
印刷版ISSN：1860-5974
电子版ISSN：1860-5974
出版年度：2012
卷号：8
期号：3
页码：1
DOI：10.2168/LMCS-8(3:31)2012
出版社：Technical University of Braunschweig
摘要：We study Boolean circuits as a representation of Boolean functions and consider different equivalence, audit, and enumeration problems. For a number of restricted sets of gate types (bases) we obtain efficient algorithms, while for all other gate types we show these problems are at least NP-hard.
其他关键词：Boolean circuits, complexity classification, isomorphism.