Threshold Logic Asymptotes
- 1 April 1970
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-19 (4) , 349-353
- https://doi.org/10.1109/t-c.1970.222921
Abstract
Let Rnmbe the number of linearly separable n-argument functions specified on some m points of the n-cube. Let R̄nmand Ṟnmbe, respectively, the minimum and maximum values attained over all choices of the m points. It is known that R̄nmn/n!. 1) Two published "simplifications" of the argument which establish this upper bound are shown to be fallacious. 2) It is proved that Ṟnm≥4m(lg m−1)/2. 3) It is proved that if m is less than exponential in n, then as n→∞, R̄nm≈(m/n)n + lower order terms. 4) Let Lnmbe the maximum number of threshold gates needed to realize an arbitrary n-argument switching function specified on m points. It is shown that Lnm≳2(m/lg m)1/2.Keywords
This publication has 9 references indexed in Scilit:
- Lower Bound of the Number of Threshold FunctionsIEEE Transactions on Electronic Computers, 1966
- Partitions ofN-Space by HyperplanesSIAM Journal on Applied Mathematics, 1966
- Bounds on the Number of Threshold FunctionsIEEE Transactions on Electronic Computers, 1966
- Threshold LogicPublished by University of California Press ,1965
- A Lower Bound of the Number of Threshold FunctionsIEEE Transactions on Electronic Computers, 1965
- Geometrical and Statistical Properties of Systems of Linear Inequalities with Applications in Pattern RecognitionIEEE Transactions on Electronic Computers, 1965
- Lower Bounds of the Number of Threshold Functions and a Maximum WeightIEEE Transactions on Electronic Computers, 1965
- Bounds on Threshold Gate RealizabilityIEEE Transactions on Electronic Computers, 1963
- Single stage threshold logicPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1961