A Uniform Circuit Lower Bound for the Permanent
Report ID: TR-426-93Author: Gore, Vivek / Allender, Eric
Date: 1993-06-00
Pages: 38
Download Formats: |Postscript|
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.