The monotone circuit complexity of Boolean functions (Q1094870): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
Created claim: DBLP publication ID (P1635): journals/combinatorica/AlonB87, #quickstatements; #temporary_batch_1731468600454 |
||
| Property / DBLP publication ID | |||
| Property / DBLP publication ID: journals/combinatorica/AlonB87 / rank | |||
Normal rank | |||
Latest revision as of 04:43, 13 November 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
