Hypergraph isomorphism and structural equivalence of Boolean functions
Hypergraph isomorphism and structural equivalence of Boolean functions
复制标题
布尔函数的超图同构和结构等价
DOI：
--
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
E. Luks
中科院分区：
文献类型：
--
作者：
E. Luks
我们证明了超图同构可以在时间O（c '）上被检验，其中n是顶点集的起始点。通常，超图的输入可能需要n（2”）空间，在这种情况下，同构检验需要多项式时间。因此，我们将检验由真值表给出的两个布尔函数是否通过变量的置换和互补而相关从而具有结构相同的网络实现的经典问题投入到多项式时间中。实际上，该方法是可并行的，我们甚至将问题带入NC。得到了单变量置换下真值表等价性的一个NC检验。
We show that hypergraph isomorphism can be tested in time O(c”), where n is the sire of the vertex set. In general, input of a hypergraph could require n(2”) space, in which case the isomorphism test is in polynomial time. As a consequence, we put into polynomial time the classic problem of testing whether two Boolean functions, given by truth tables, are related via permutations and complementations of the variables, and therefore have structurally identical network realizations. In fact, the method is parallelizable and we put the problem even into NC. We obtain similarly an NC test of equivalence of truth tables under permutation of variables alone.