On Reduction of Computations for Threshold Function Identification

Knowing a sufficient and necessary condition for being a threshold function (TF) is quite crucial for TF identification algorithm. However, to the best of our knowledge, no one proposed an efficient sufficient and necessary condition for being a TF. Hence, the state-of-the-art approach to this identification problem exploits a necessary condition, and a weight and threshold value assignment approach to identify TFs instead. In fact, a sufficient and necessary condition for being a TF had been proposed many decades ago, which is called the Summable Theorem. However, this theorem and the corresponding checking algorithm are not practical from the viewpoint of efficiency due to the high complexity. As a result, in this work, we propose several theorems such that the complexity of the TF identification algorithm can be significantly reduced. Furthermore, according to the experimental results, 76%similar to 96% computations are saved on average, and 40%similar to 75% CPU time are saved on average, for a set of 6-input similar to 9-input unate functions.