|
This article is cited in 7 scientific papers (total in 7 papers)
Combinatorial-probability and geometric methods in threshold logic
Yu. A. Zuev
Abstract:
We consider the problem of estimating the number $N_n$ of threshold functions in $n$ variables. The following estimates, asymptotic with respect to $n$, were obtained earlier for the logarithm of this number: $n^2/2\lesssim\log_2N_n\lesssim n^2$. We prove a lemma connecting the number of regions into which the $n$-dimensional Euclidean space is partitioned by a finite set of hyperplanes, with the number of affine subspaces that are generated by the intersections of the hyperplanes. By means of this lemma we prove that for sufficiently large $n$ the inequality $\log_2N_n>n^2(1-10/\ln n)$ holds. In the same way we establish the asymptotic formula $\log_2N_n\\thicksim n^2$, $n\to\infty$.
We introduce the concept of the graph of threshold functions and show the asymptotics for $\log _2N_n(M)$ for various $M$, where $N_n(M)$ is the number of threshold functions with $M$ units.
Received: 08.05.1990
Citation:
Yu. A. Zuev, “Combinatorial-probability and geometric methods in threshold logic”, Diskr. Mat., 3:2 (1991), 47–57; Discrete Math. Appl., 2:4 (1992), 427–438
Linking options:
https://www.mathnet.ru/eng/dm786 https://www.mathnet.ru/eng/dm/v3/i2/p47
|
Statistics & downloads: |
Abstract page: | 801 | Full-text PDF : | 369 | First page: | 1 |
|