A Group Algebraic Approach to NPN Classification of Boolean Functions
We would like to thank the National Natural Science Foundation of China (Grant No. 61572109) and the Special Fund for Bagui Scholars of Guangxi for the technology support
Theory of Computing Systems
The classification of Boolean functions plays an underpinning role in logic design and synthesis of VLSI circuits. This paper considers a underpinning question in Boolean function classification: how many distinct classes are there for k-input Boolean functions. We exploit various group algebraic properties to efficiently compute the number of unique equivalent classes. We have reduced the computation complexity from 2mm! to (m + 1)!. We present our analysis for NPN classification of Boolean functions with up to ten variables and compute the number of NP and NPN equivalence classes for 3-10 variables. This is the first time to report the number of NP and NPN classifications for Boolean functions with 9-10 variables. We demonstrate the effectiveness of our method by both theoretical proofs and numeric experiments.
Locate the Document
Zhang, J., Yang, G., Hung, W. N. N., Liu, T., Song, X., & Perkowski, M. A. (2019). A Group Algebraic Approach to NPN Classification of Boolean Functions. Theory of Computing Systems, 63(6), 1278–1297.