Expressibility and Nonuniform Complexity Classes
Burkhard Molzan · SIAM Journal on Computing · 1990
A framework that admits: the characterization of nonuniform complexity classes in terms of logical expressibility is presented. In the case of classes that are defined by means of bounded-depth Boolean circuits, group theoretic characterizations given by Barrington and Thérien (see [Proc. 19th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, New York, 1987, pp. 101–109]) are exploited. This approach extends previous results of Immerman [Proc. 15th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, New York, 1983, pp. 347–354] and Gurevich and Lewis [Inform. and Control, 61 (1984), pp. 65–74], and provides a unique fashion of proofs for the results. In the last section the computing power of generalized branching programs is related to logical expressibility.