초록 close

*본 연구는 2007년도 국민대학교 교내연구비를 지원받아 수행되었음.


D-class computation requires multiplication of three Boolean matrices for each of all possible triples of Boolean matrices and search for equivalent Boolean matrices according to a specific equivalence relation. It is easy to see that even multiplying all 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 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.