Details

Autor(en) / Beteiligte

• Kutz, Martin

Titel

The Complexity of Boolean Matrix Root Computation

Ist Teil von

• Computing and Combinatorics, 2003, p.212-221

Ort / Verlag

Berlin, Heidelberg: Springer Berlin Heidelberg

Erscheinungsjahr

2003

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• 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.