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
    0 references
    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

    Identifiers