# On the Descriptive Complexity of Color Coding +
## 2 Describing Parameterized Problems
### Bounded Rank Reductions  
To complete the formal framework for describing parameterized problems, we need a notion of parameterized reductions that is very weak to ensure that the smallest class we study, para-AC\({}^{0}\), is closed under them. Such a reduction is used in the literature [5], boringly named para-AC\({}^{0}\)-reduction, but both its definition as well as the definition of other kinds of parameterized reductions found in the literature do not fit well with our logical framework: The reductions are defined in terms of machines or circuits that get as input a string that explicitly or implicitly contains the parameter \(k\) and output a new problem instance that once more explicitly or implicitly contains a new parameter value \(k^{\prime}\). In contrast, in our setting the inputs and outputs must be logical structures that we wish to define in terms of formulas. Furthermore, \"outputting a parameter value\" is difficult in our formal framework since parameter values are not elements of the universe, but indices of the formulas. All of these problems can be circumvented, see for instance ([11], Definition 5.3), but we believe it gives a cleaner formalism to give a new \"purely logical\" definition of reductions between parameterized problems. We will not prove this, but remark that the power of this reduction is the same as that of para-AC\({}^{0}\)-reductions. **Definition 1**. : _Let \(\tau\) and \(\tau^{\prime}\) be signatures and let \(Q\subseteq\textsc{struc}[\tau]\times\mathbb{N}\) and \(Q^{\prime}\subseteq\textsc{struc}[\tau^{\prime}]\times\mathbb{N}\) be two problems. A bounded rank reduction from \(Q\) to \(Q^{\prime}\), written \(Q\leq_{\operatorname{br}}Q^{\prime}\), is a pair of families \((f_{k})_{k\in\mathbb{N}}\) and \((\iota_{k^{\prime}})_{k^{\prime}k^{\prime}\in\mathbb{N}}\) where_  
* _each_ \(f_{k}\) _is a first-order query from_ \(\tau\)_-structures to_ \(\tau^{\prime}\)_-structures and_
* _each_ \(\iota_{k,k^{\prime}}\) _is a_ \(\tau\)_-formula_  
_such that_  
1. _for each_ \((\mathcal{A},k)\in\textsc{struc}[\tau]\times\mathbb{N}\) _there is exactly one_ \(k^{\prime}\in\mathbb{N}\)_, denoted by_ \(\iota_{k}(\mathcal{A})\) _in the following, such that_ \(\mathcal{A}\models\iota_{k,k^{\prime}}\)_,_
2. _there is a mapping_ \(\iota^{*}\colon\mathbb{N}\to\mathbb{N}\) _such that for all_ \(\mathcal{A}\in\textsc{struc}[\tau]\) _we have_ \(\iota_{k}(\mathcal{A})\leq\iota^{*}(k)\)_,_
3. \((\mathcal{A},k)\in Q\) _and only if_ \((f_{k}(\mathcal{A}),\iota_{k}(\mathcal{A}))\in Q^{\prime}\)_, and_
4. _the quantifier rank of all_ \(\iota_{k,k^{\prime}}\) _and of all formulas inside the_ \(f_{k}\) _and of the widths of each_ \(f_{k}\) _is bounded by a constant_ \(c\)_._  
Let us briefly explain the ingredients of this definition: Each \(f_{k}\) maps all \(\tau\)-structures \(\mathcal{A}\) to \(\tau^{\prime}\)-structures \(\mathcal{A}^{\prime}\). The fact that we have one function for each parameter value allows us to make our mapping depend on the parameter. The job of the formulas \(\iota_{k,k^{\prime}}\) is solely to \"compute\" the new parameter value \(k^{\prime}\), based not only on the original value \(k\), but also on \(\mathcal{A}\). If, as is the case in many reductions, the new parameter value \(k^{\prime}\) just depends on \(k\) (typically, it even is \(k\)), we can just set \(\iota_{k,k^{\prime}}\) to a trivial tautology \(\top\) and all other \(\iota_{k,k^{\prime\prime}}\) to the contradiction \(\bot\). In the definition, we referred to first-order queries, which are a standard way of defining a logical \(\tau^{\prime}\)-structure in terms of a \(\tau\)-structure in database theory and finite model theory (we remark that in general model theory \"interpretation\" is used instead of \"query\"and that \"transductions\" from fpt-theory are queries with special semantic and syntactic properties).