Efficient prime factorization of logic expressions

摘要

The set of multivariate Boolean functions over the variables &khgr;1 …, &khgr;m is considered as the set of multilinear polynomials with coefficients in [0,1] over the literals {&khgr;1, &khgr;1, …, &khgr;m, &khgr;m}. We denote this set of polynomials as B[@@@@], and call the set of polynomial operations over them algebraic operations. It is shown that these polynomials, called logic expressions, have a unique algebraic prime factorization. An &Ogr;(n log2 n) algorithm to find this factorization is presented. An improvement to the algorithm is presented which may reduce its average-case complexity to &Ogr;(n).