# A Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy
## 2 Preliminaries
### Parameterized Complexity
\begin{array}{|l|}\text{$p$-$W$Sat}[\mathcal{C}]\\ \text{\emph{Instance:} A Boolean circuit $C\in\mathcal{C}$, and an integer $k$.}\\ \text{\emph{Parameter:} $k$.}\\ \text{\emph{Question:} Does there exist an assignment of weight $k$ that satisfies C?}\\ \end{array} \)  
We denote closure under fpt-reductions by \([\ \cdot\ ]^{\text{fpt}}\)--that is, for any set \(\mathcal{L}\) of parameterized problems, \([\ \mathcal{L}\ ]^{\text{fpt}}\) is the set of all parameterized problems \(L^{\prime}\) that are fpt-reducible to some problem \(L\in\mathcal{L}\). The classes \(\text{W}[t]\) are defined by letting \(\text{W}[t]=[\ \{\ \text{$p$-$W$SAT}[\textsc{circ}_{t,\mu}]:u\geq 1\ \}\ ]^{\text{fpt}}\) for all \(t\geq 1\). The classes \(\text{W}[\text{SAT}]\) and \(\text{W}[\text{P}]\) are defined by letting \(\text{W}[\text{SAT}]=[\ \text{$p$-$W$SAT}[\textsc{form}]\ ]^{\text{fpt}}\) and \(\text{W}[\text{P}]=[\ \text{$p$-$W$SAT}[\textsc{circ}]\ ]^{\text{fpt}}\). Let \(K\) be a classical complexity class, e.g., \(\text{NP}\). The parameterized complexity class para-K is defined as the class of all parameterized problems \(L\subseteq\Sigma^{*}\times\mathbb{N}\), for some finite alphabet \(\Sigma\), for which there exist a computable function \(f:\mathbb{N}\rightarrow\Sigma^{*}\), and a problem \(P\subseteq\Sigma^{*}\) such that \(P\in K\) and for all instances \((x,k)\in\Sigma^{*}\times\mathbb{N}\) of \(L\) we have that \((x,k)\in L\) if and only if \((x,f(k))\in P\). (Here, we implicitly use a representation of pairs of strings in \(\Sigma^{*}\times\Sigma^{*}\) as strings in \(\Sigma^{*}\).) Intuitively, the class para-K consists of all problems that are in \(K\) after a precomputation that only involves the parameter. The class para-NP can also be defined via nondeterministic fpt-algorithms [24]. The class para-K can be seen as a direct analogue of the class K in parameterized complexity. In particular, for the case of \(\text{K}=\text{P}\), we have \(\text{FPT}=\text{para-P}\). We consider the following (trivial) parameterization of SAT, the satisfiability problem for propositional logic. We let \(\text{SAT}_{1}=\{\ (\varphi,1):\varphi\in\text{SAT}\ \}\). In other words, \(\text{SAT}_{1}\) is the parameterized variant of SAT where the parameter is the constant value \(1\). Similarly, we let \(\text{UNSAT}_{1}=\{\ (\varphi,1):\varphi\in\text{SAT}\ \}\). We say that a truth assignment for a Boolean circuit has _weight_\(k\) if it sets exactly \(k\) of the variables of the circuit to true. We denote the class of Boolean circuits with depth \(u\) and weft \(t\) by \(\textsc{circ}_{t,\mu}\). We denote the class of all Boolean circuits by \(\textsc{circ}_{t,\mu}\), and the class of all Boolean formulas by \(\textsc{circ}_{t,\mu}\). We denote the class of all Boolean formulas by \(\textsc  
UNSAT }. The problem SAT\({}_{1}\) is para-NP-complete, and the problem UNSAT\({}_{1}\) is para-co-NP-complete. In other words, the class para-NP consists of all parameterized problems that can be fpt-reduced to SAT\({}_{1}\), and para-co-NP consists of all parameterized problems that can be fpt-reduced to UNSAT\({}_{1}\). Another analogue to the classical complexity class K is the parameterized complexity class \(\text{XK}^{\text{nu}}\), that is defined as the class of those parameterized problems \(Q\) whose slices \(Q_{k}\) are in K, i.e., for each positive integer \(k\) the classical problem \(Q_{k}=\{\,x:(x,k)\in Q\,\}\) is in K [20]. For instance, the class \(\text{XP}^{\text{nu}}\) consists of those parameterized problems whose slices are decidable in polynomial time. Note that this definition is non-uniform, that is, for each positive integer \(k\), there might be a completely different polynomial-time algorithm that witnesses that \(Q_{k}\) is polynomial-time solvable. There are also uniform variants XK of these classes \(\text{XK}^{\text{nu}}\).