Name
Abstract | ||
|---|---|---|
An extremal point of a positive threshold Boolean function $f$ is either a maximal zero or a minimal one. It is known that if $f$ depends on all its variables, then the set of its extremal points completely specifies $f$ within the universe of threshold functions. However, in some cases, $f$ can be specified by a smaller set. The minimum number of points in such a set is the specification number of $f$. It was shown in [S.-T. Hu. Threshold Logic, 1965] that the specification number of a threshold function of $n$ variables is at least $n+1$. In [M. Anthony, G. Brightwell, and J. Shawe-Taylor. On specifying Boolean functions by labelled examples. Discrete Applied Mathematics, 1995] it was proved that this bound is attained for nested functions and conjectured that for all other threshold functions the specification number is strictly greater than $n+1$. In the present paper, we resolve this conjecture negatively by exhibiting threshold Boolean functions of $n$ variables, which are non-nested and for which the specification number is $n+1$. On the other hand, we show that the set of extremal points satisfies the statement of the conjecture, i.e., a positive threshold Boolean function depending on all its $n$ variables has $n+1$ extremal points if and only if it is nested. To prove this, we reveal an underlying structure of the set of extremal points. |
Year | Venue | DocType |
|---|---|---|
2017 | ALT | Conference |
Volume | Citations | PageRank |
abs/1706.01747 | 1 | 0.37 |
References | Authors | |
5 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| V. V. Lozin | 1 | 54 | 4.23 |
| Igor Razgon | 2 | 537 | 35.41 |
| Victor Zamaraev | 3 | 18 | 9.64 |
| Elena Zamaraeva | 4 | 1 | 0.71 |
| Nikolai Yu. Zolotykh | 5 | 3 | 1.76 |