查看文章

This paper describes a family of depth-universal circuits. For any n, c, d there is a universal circuit that can simulate any circuit having n inputs, of size c and depth d, and U has depth and size . The construction is used to give an alternative proof of a theorem of Ruzzo showing the invariance under different uniformity conditions of complexity classes defined by uniform circuit families.