Identification of a Threshold Function (TF) is a significant task that determines whether a given Boolean function is a TF or not. The state-of-the-art only identifies all 8-input NP-class TFs. In this paper, we propose a new necessary condition for a function being a representative NP-class TF. With the proposed necessary condition, we design an effective approach to identify 9-input NP-class TFs. As a result, we reduce the candidate set of 9-input functions being TFs to an extremely tiny subset of all 9-input Boolean functions. Experimental results show that our approach successfully identifies at least 80% of 9-input NP-class TFs. This is the first attempt to deal with this challenging problem in the literature.

Threshold Function (TF) is a subset of Boolean function that can be represented with a single linear threshold gate (LTG). In the research about threshold logic, the identification of TF is an important task that determines whether a given function is a TF or not. In this article, we propose a sufficient and necessary condition for a function being a TF. With the proposed sufficient and necessary condition, we devise a TF identification algorithm. The experimental results show that the proposed approach saves 80% CPU time for identifying all the 8-input NP-class TFs as compared with the state-of-the-art. Furthermore, the LTGs corresponding to the identified TFs obtained by the proposed approach have smaller weights and threshold values than the state-of-the-art.