Quick links

A Uniform Circuit Lower Bound for the Permanent

Report ID:
TR-426-93
Date:
May 1993
Pages:
38
Download Formats:

Abstract:

We show that uniform families of ACC circuits of subexponential size
cannot compute the permanent function. This also implies similar lower
bounds for certain sets in PP.
This is one of the very few examples
of a lower bound in circuit complexity whose proof hinges on the
uniformity condition; it is still unknown if there is
any set in Ntime ($2^{n^{O(1)}}$) that does not have nonuniform ACC circuits.

Follow us: Facebook Twitter Linkedin