효율적인 D-클래스 계산을 위한 알고리즘

Algorithm for Efficient D-Class Computation

  D-class computation requires multiplication of three Boolean matrices for each of all possible triples of n×n Boolean matrices and search for equivalent n×n Boolean matrices according to a specific equivalence relation. It is easy to see that even multiplying all n×n Boolean matrices with themselves shows exponential time complexity and D-Class computation was left an unsolved problem due to its computational complexity. The vector-based multiplication theory shows that the multiplication of three Boolean matrices for each of all possible triples of n×n Boolean matrices can be done much more efficiently. However, D-Class computation requires computation of equivalent classes in addition to the efficient multiplication. The paper discusses a theory and an algorithm for efficient D-class computation, and shows execution results of the algorithm.