The monotone circuit complexity of Boolean functions (Q1094870): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claims |
||
| Property / author | |||
| Property / author: Noga Alon / rank | |||
| Property / reviewed by | |||
| Property / reviewed by: Leon Livovschi / rank | |||
Revision as of 08:40, 10 February 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
