A 2.5 n lower bound on the monotone network complexity of \(T^ n_ 3\) (Q798294)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A 2.5 n lower bound on the monotone network complexity of \(T^ n_ 3\) |
scientific article; zbMATH DE number 3869223
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A 2.5 n lower bound on the monotone network complexity of \(T^ n_ 3\) |
scientific article; zbMATH DE number 3869223 |
Statements
A 2.5 n lower bound on the monotone network complexity of \(T^ n_ 3\) (English)
0 references
1985
0 references
Let \(X_ N=\{x_ 1,x_ 2,...,x_ N\}\) be a set of N Boolean variables. The k-th threshold function over \(X_ N\) (denoted \(T^ N_ k(X_ N))\) is the monotone Boolean function defined to be 1 if and only if at least k of its arguments are 1. In this paper we prove that any monotone Boolean network computing \(T^ N_ 3(X_ N)\) contains at least 2.5N-5.5 gates.
0 references
monotone network complexity
0 references
threshold function
0 references
monotone Boolean function
0 references
monotone Boolean network
0 references
