Quasipolynomial size circuit classes
David A. Mix Barrington · 2003
Circuit complexity theory has tried to understand which problems can be solved by 'small' circuits of constant depth. Normally 'small' has meant 'polynomial in the input size', but a number of recent results have dealt with circuits of size 2 to the log n/sup 0(1)/ power, or quasipolynomial size. The author summarizes the reasons for thinking about the complexity classes so introduced, surveys these results and gives an overview of these classes. He also shows that the Barrington-Immerman-Straubing uniformity definition for polynomial-size classes can easily be extended to quasipolynomial size as well, with most of the key results remaining true in the uniform setting.>