Descriptive complexity of circuit-based counting classes

Abstract

In this thesis, we study the descriptive complexity of counting classes based on Boolean circuits. In descriptive complexity, the complexity of problems is studied in terms of logics required to describe them. The focus of research in this area is on identifying logics that can express exactly the problems in specific complexity classes. For example, problems are definable in ESO, existential second-order logic, if and only if they are in NP, the class of problems decidable in nondeterministic polynomial time. In the computation model of Boolean circuits, individual circuits have a fixed number of inputs. Circuit families are used to allow for an arbitrary number of input bits. A priori, the circuits in a family are not uniformly described, but one can impose this as an additional condition, e.g., requiring that there is an algorithm constructing them. For any circuit there is a function counting witnesses (or proofs) for the circuit producing the output 1. Consequently, any class of Boolean circuits has a corresponding class of counting functions.

We characterize counting classes in terms of counting winning strategies in the model-checking game for different logics extending first-order logic, namely the classes #AC⁰, #NC¹, #SAC¹, and #AC¹. These classes restrict circuits to constant or logarithmic depth and in some cases also with respect to the fan-in of gates. In the case of the logarithmic-depth classes, this also requires new characterizations of the corresponding classes of Boolean circuit, as known results do not seem suitable for this approach. Our characterization of #AC⁰ also leads to a new characterization of the related class TC⁰. Our results apply both in the non-uniform as well as the uniform setting.

We put our new characterization of #AC⁰ into perspective by studying connections to another logic-based counting class, #FO. This class is known to coincide with #P, the class of functions counting the number of accepting computation paths of NP-machines. We study a variant of #FO and the alternation hierarchy inside this class, as well as its connections to the class #AC⁰.

Finally, we observe that often it is easier to characterize non-uniform circuit complexity classes than their uniform counterparts. This lends hope to the idea that characterizations of uniform classes could directly imply corresponding results in the non-uniform setting. We prove that this is true for a wide variety of classes, in particular for all classes we consider in this thesis.