The complexity of Boolean matrix root computation
The complexity of Boolean matrix root computation
复制标题
DOI：
10.1016/j.tcs.2004.02.041
复制
发表时间：
2004-10-06
影响因子：
1.1
通讯作者：
Kutz, M
中科院分区：
文献类型：
--
作者：
Kutz, M
我们证明了寻找布尔矩阵的根是一个 NP 难题。这回答了半群理论中一个 20 年前的问题。将布尔矩阵解释为有向图，我们进一步揭示了布尔矩阵根与图同构之间的联系，这证明了对于与细分有向图相关的布尔矩阵的某个子类，求根与图同构问题具有相同的复杂性。 (C) 2004 Elsevier B.V. 保留所有权利。
We show that finding roots of Boolean matrices is an NP-hard problem. This answers a 20 year old question from semigroup theory. Interpreting Boolean matrices as directed graphs, we further reveal a connection between Boolean matrix roots and graph isomorphism, which leads to a proof that for a certain subclass of Boolean matrices related to subdivision digraphs, root finding is of the same complexity as the graph-isomorphism problem. (C) 2004 Elsevier B.V. All rights reserved.