The monotone circuit complexity of Boolean functions (Q1094870): Difference between revisions
From MaRDI portal
Removed claims |
Changed an Item |
||
| Property / author | |||
| Property / author: Noga Alon / rank | |||
Normal rank | |||
| Property / reviewed by | |||
| Property / reviewed by: Leon Livovschi / rank | |||
Normal 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
