On the constructive characterization of threshold functions |
| |
Authors: | A P Sokolov |
| |
Institution: | 1.Moscow State University,Moscow,Russia |
| |
Abstract: | In this paper, the structure of the set of threshold functions and complexity problems are considered. The notion of the signature
of a threshold function is defined. It is shown that if a threshold function essentially depends on all of its variables,
then the signature of this function is unique. The set of threshold functions is partitioned into classes with equal signatures.
A theorem characterizing this partition is proved. The importance of the class of monotone threshold functions is emphasized.
The complexity of transferring one threshold function specified by a linear form into another is examined. It is shown that
in the worst case this transfer would take exponential time. The structure of the set of linear forms specifying the same
threshold function is also examined. It is proved that for any threshold function this set of linear forms has a unique basis
in terms of the operation of addition of linear forms. It is also shown that this basis is countable. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|