# A Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy
## 2 Preliminaries
### Parameterized Complexity  
We introduce some core notions from parameterized complexity theory. For an in-depth treatment, we refer to other sources [19; 20; 21; 22; 23]. A _parameterized problem_\(L\) is a subset of \(\Sigma^{*}\times\mathbb{N}\) for some finite alphabet \(\Sigma\). For an instance \((x,k)\in\Sigma^{*}\times\mathbb{N}\), we call \(x\) the _main part_ and \(k\) the _parameter_. The following generalization of polynomial-time computability is commonly regarded as the main tractability notion of parameterized complexity theory. A parameterized problem \(L\) is _fixed-parameter tractable_ if there exists a computable function \(f\) and a constant \(c\) such that there exists an algorithm that decideswhether \((x,k)\in L\) in time \(f(k)\cdot|x|^{c}\), where \(|x|\) denotes the size of \(x\). Such an algorithm is called an _fpt-algorithm_, and this amount of time is called _fpt-time_. FPT is the class of all parameterized problems that are fixed-parameter tractable. If the parameter is constant, then fpt-algorithms run in polynomial time where the order of the polynomial is independent of the parameter. This provides a good scalability in the parameter in contrast to running times of the form \(|x|^{k}\), which are also polynomial for fixed \(k\), but are already impractical for, say, \(k>5\). Parameterized complexity also generalizes the notion of polynomial-time reductions. Let \(L\subseteq\Sigma^{*}\times\mathbb{N}\) and \(L^{\prime}\subseteq(\Sigma^{\prime})^{*}\times\mathbb{N}\) be two parameterized problems. A _(many-one) fpt-reduction_ from \(L\) to \(L^{\prime}\) is a mapping \(R:\Sigma^{*}\times\mathbb{N}\rightarrow(\Sigma^{\prime})^{*}\times\mathbb{N}\) from instances of \(L\) to instances of \(L^{\prime}\) for which there exist some computable function \(g:\mathbb{N}\rightarrow\mathbb{N}\) such that for all \((x,k)\in\Sigma^{*}\times\mathbb{N}\): (i) \((x,k)\) is a yes-instance of \(L\) if and only if \((x^{\prime},k^{\prime})=R(x,k)\) is a yes-instance of \(L^{\prime}\), (ii) \(k^{\prime}\leq g(k)\), and (iii) \(R\) is computable in fpt-time. Let K be a parameterized complexity class. A parameterized problem \(L\) is K-_hard_ if for every \(L^{\prime}\in\text{K}\) there is an fpt-reduction from \(L^{\prime}\) to \(L\). A problem \(L\) is K-_complete_ if it is both in K and K-hard. Reductions that satisfy properties (i) and (ii) but that are computable in time \(O(|x|^{f(k)})\), for some fixed computable function \(f\), we call _xp-reductions_. The parameterized complexity classes \(\text{W}[\text{t}]\), for \(t\geq 1\), \(\text{W}[\text{SAT}]\), and \(\text{W}[\text{P}]\) can be used to give evidence that a given parameterized problem is not fixed-parameter tractable. These classes are based on the satisfiability problems of Boolean circuits and formulas. We consider _Boolean circuits_ with a single output gate. We call input nodes _variables_. We distinguish between _small_ gates, with fan-in \(\leq 2\), and _large gates_, with fan-in \(>2\). The _depth_ of a circuit is the length of a longest path from any variable to the output gate. The _weft_ of a circuit is the largest number of large gates on any path from a variable to the output gate. We say that a circuit \(C\) is in _negation normal form_ if all negation nodes in \(C\) have variables as inputs. A _Boolean formula_ can be considered as a Boolean circuit where all gates have fan-out \(\leq 1\). We adopt the usual notions of truth assignments and satisfiability of a Boolean circuit. 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}\), and the class of all Boolean formulas by \(\textsc{form}\). For any class \(\mathcal{C}\) of Boolean circuits, we define the following parameterized problem:  
\(