The monotone circuit complexity of Boolean functions (Q1094870): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Revision as of 02:12, 5 March 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The monotone circuit complexity of Boolean functions |
scientific article |
Statements
The monotone circuit complexity of Boolean functions (English)
0 references
1987
0 references
Some new results concerning lower bounds for the complexity of monotone circuits that detect cliques in graphs are obtained using modified versions of known methods. It is shown that even a very rough approximation of the maximum clique size of a graph, requires superpolynomial size of monotone circuits. Also, lower bounds are given for some Boolean functions and a largest lower bound for an NP-function of n variables is obtained.
0 references
superpolynomial lower bound
0 references
exponential lower bound
0 references
complexity of monotone circuits
0 references
cliques
0 references
Boolean functions
0 references
NP-function
0 references
