# On the Descriptive Complexity of Color Coding +
## 2 Describing Parameterized Problems
### Parameterized Circuits  
For our descriptive setting, we need to slightly adapt the definition of the circuit classes \(\textsc{para-AC}^{0}\) and \(\textsc{para-AC}^{0\uparrow}\) from [5,7]: Let us say that a problem \(Q\subseteq\textsc{struc}[\tau]\times\mathbb{N}\) is in \(\textsc{para-AC}^{0}\), if there is a family \((C_{n,k})_{n,k\in\mathbb{N}}\) of AC-circuits (Boolean circuits with unbounded fan-in) such that for all \((\mathcal{A},k)\in\textsc{struc}[\tau]\times\mathbb{N}\) we have  
1. \((\mathcal{A},k)\in Q\) if and only if \(C_{|x|,k}(x)=1\) where \(x\) is a binary encoding of \(\mathcal{A}\) and \(|x|\) is the length of the encoding,
2. the size of each \(C_{n,k}\) is at most \(f(k)\cdot n^{c}\) for some function \(f\) and some constant \(c\) that is independent of both \(n\) and \(k\),
3. the depth of each \(C_{n,k}\) is bounded by some constant that is again independent of both \(n\) and \(k\), and
4. the circuit family satisfies a \(\textsc{dlogtime-uniformity}\) condition. (Since the complex questions around circuit uniformity are not of special importance for the present paper, we keep its discussion short and just remark that \(\textsc{dlogtime-uniformity}\) roughly means that arithmetic formulas suffice to describe the circuits.) The class \(\textsc{para-AC}^{0\uparrow}\) is defined the same way, but the depth may be \(g(k)\) for some \(g\) instead of only \(O(1)\). The following fact and theorem show how these two circuit classes are closely related to descriptions of parameterized problems using formulas:  
**Fact 1** ([4]). : \(\textsc{para-AC}^{0}=\textsc{X}\big{\{}(\phi_{k})_{k\in\mathbb{N}}\mid\phi_{k} \in\textsc{FO}[+,\times],\max_{k}\textsc{qr}(\phi_{k})<\infty\big{\}}.\)__  
**Theorem 1**. : \(\textsc{para-AC}^{0\uparrow}=\textsc{X}\big{\{}(\phi_{k})_{k\in\mathbb{N}}\mid \phi_{k}\in\textsc{FO}[+,\times],\max_{k}\lvert\textsc{bound}(\phi_{k})\rvert< \infty\big{\}}.\)__Proof. : The basic idea behind the proof is quite \"old.\" We wish to establish links between circuit depth and size and the number of variables used in a formula--and such links are well-known, see for instance [15]: The quantifier rank of a first-order formula naturally corresponds to the depth of a circuit that solves the model checking problem for the formula. The number of variables corresponds to the exponent of the polynomial that bounds the size of the circuit (the paper [16] is actually entitled \"\(\text{\rm DSPACE}[n^{k}]=\text{\rm VAR}[k+1]\)\"). One thing that is usually not of interest (because only one formula is usually considered) is the fact that the length of the formula is linked multiplicatively to the size of the circuit. In detail, suppose we are given a problem \(Q\subseteq\text{\rm struct}[\tau]\times\mathbb{N}\) with \(Q\in\text{\rm para-AC}^{0\dagger}\) via a circuit family \((C_{n,k})_{n,k\in\mathbb{N}}\) of depth \(g(k)\) and size \(f(k)n^{c}\). For a fixed \(k\), we now need to construct a formula \(\phi_{k}\) that correctly decides the \(k\)-th slice. In other words, we need an \(\text{\rm FO}[+,\times]\)-formula \(\phi_{k}\) whose finite models are exactly those on which the family \((C_{n,k})_{n\in\mathbb{N}}\) (note that \(k\) no longer indexes the family) evaluates to \(1\) (when the models are encoded as bitstrings). It is well-known how such a formula can be constructed, see for instance [15], we just need a closer look at how the quantifier rank and number of variables relate to the circuit depth and size. The basic idea behind the formula \(\phi_{k}\) is the following: The circuit has \(f(k)n^{c}\) gates and we can \"address\" these gates using \(c\) variables (which gives us \(n^{c}\) possibilities) plus a number \(i\in\{1,\ldots,f(k)\}\) (which gives us \(f(k)\cdot n^{c}\) possibilities). Since for fixed \(k\) the number \(f(k)\) is also fixed, it is permissible that the formula \(\phi_{k}\) contains \(f(k)\) copies of some subformula, where each subformula handles another value of \(i\).