The complexity of Boolean matrix root computation

Abstract. We show that finding roots of Boolean matrices is an NPhard problem. This answers a twenty 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.