A Superpolynomial Lower Bound for a Circuit Computing the Clique Function with at most (1/6)log log <i>n</i> Negation Gates (Q5700577)
From MaRDI portal
scientific article; zbMATH DE number 2220467
Language | Label | Description | Also known as |
---|---|---|---|
English | A Superpolynomial Lower Bound for a Circuit Computing the Clique Function with at most (1/6)log log <i>n</i> Negation Gates |
scientific article; zbMATH DE number 2220467 |
Statements
A Superpolynomial Lower Bound for a Circuit Computing the Clique Function with at most (1/6)log log <i>n</i> Negation Gates (English)
0 references
28 October 2005
0 references
circuit complexity
0 references
monotone circuit
0 references
negation-limited circuit
0 references
approximation method
0 references
lower bound
0 references
clique function
0 references