# A Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy
## 2 Preliminaries
### Fpt-Reductions to SAT and Parameterized Complexity Classes at Higher Levels of the Ph  
Problems in NP and co-NP can be encoded into SAT in such a way that the time required to produce the encoding and consequently also the size of the resulting SAT instance are polynomial in the input (the encoding is a polynomial-time many-one reduction). Typically, the SAT encodings of problems proposed for practical use are of this kind (see, e.g., [27]). For problems that are \"beyond NP\", say for problems on the second level of the PH, such polynomial SAT encodings do not exist, unless the PH collapses. However, for such problems, there still could exist SAT encodings which can be produced in fpt-time with respect to some parameter associated with the problem. In fact, such fpt-time SAT encodings have been obtained for various problems on the second level of the PH [28; 29; 30; 31]. The classes para-NP and para-co-NP contain exactly those parameterized problems that admit such a many-one fpt-reduction to SAT\({}_{1}\) and UNSAT\({}_{1}\), respectively. Thus, with fpt-time encodings, one can go significantly beyond what is possible by conventional polynomial-time SAT encodings. \(\Sigma_{2}^{\text{P}}[k\ast]\)-\(\text{WSat}(\mathcal{C})\)  
_Instance:_ A quantified Boolean formula \(\exists X.\forall Y.\psi\), and an integer \(k\). _Parameter:_\(k\). _Question:_ Does there exist a truth assignment \(\alpha\) to \(X\) with weight \(k\) such that for all truth assignments \(\beta\) to \(Y\) the assignment \(\alpha\cup\beta\) satisfies \(\psi\)? Similarly, the problem \(\Sigma_{2}^{\text{P}}[\ast k]\)-\(\text{WSat}(\mathcal{C})\) provides the foundation for the \(\ast\)-\(k\) hierarchy--where \(\mathcal{C}\) is a class of Boolean circuits. (The parameterized problems \(\Sigma_{2}^{\text{P}}[\ast k]\)-\(\text{WSat}(\mathcal{C})\) seem not to be fpt-reducible to each other for various classes \(\mathcal{C}\) of Boolean circuits--similarly to the problems \(p\)-\(\text{WSat}[\mathcal{C}]\) that are used to define the classes \(\mathsf{W}[t]\), \(\mathsf{W}[\text{SAT}]\), and \(\mathsf{W}[\text{P}]\). This is in contrast to the case of \(\Sigma^{\text{P}}_{2}[\![*]\! ]\)-\(\mathsf{WSat}\), where we can use a Tseitin transformation [32] to reduce arbitrary Boolean circuits to equisatisfiable 3 CNF formulas.) \( \begin{array}{l}\boxed{\Sigma^{\text{P}}_{2}[*k]\text{-}\mathsf{WSat}( \mathcal{C})}\end{array} \)  
_Instance:_ A Boolean circuit \(C\in\mathcal{C}\) over two disjoint sets \(X\) and \(Y\) of variables, and an integer \(k\). _Parameter:_\(k\). _Question:_ Does there exist a truth assignment \(\alpha\) to \(X\) such that for all truth assignments \(\beta\) to \(Y\) with weight \(k\) the assignment \(\alpha\cup\beta\) satisfies \(C\)? The parameterized complexity class \(\Sigma^{\text{P}}_{2}[k*]\) (also called the \(k\)-\(*\) class) is then defined as follows:  
\( \begin{array}{l}\Sigma^{\text{P}}_{2}[k*]=\quad[\;\Sigma^{\text{P}}_{2}[k*] \text{-}\mathsf{WSat}\;]^{\text{fpt}}.\end{array} \)  
Similarly, the classes of the \(*\)-\(k\) hierarchy are defined as follows:  
\( \begin{array}{l}\Sigma^{\text{P}}_{2}[*k,t]=\quad[\;\{\,\Sigma^{\text{P}}_{2 }[*k]\text{-}\mathsf{WSat}(\textsc{circ}_{t,u}):u\geq 1\;\}\;]^{\text{fpt}},\\ \Sigma^{\text{P}}_{2}[*k,\text{SAT}]=\quad[\;\Sigma^{\text{P}}_{2}[*k]\text{-} \mathsf{WSat}(\textsc{form})\;]^{\text{fpt}},\text{ and}\\ \Sigma^{\text{P}}_{2}[*k,\text{P}]=\quad[\;\Sigma^{\text{P}}_{2}[*k]\text{-} \mathsf{WSat}(\textsc{circ})\;]^{\text{fpt}}.\end{array} \)  
Note that these definitions are entirely analogous to those of the parameterized complexity classes of the W-hierarchy [20]. The following inclusion relations hold between the classes of the \(*\)-\(k\) hierarchy:  
\( \begin{array}{l}\Sigma^{\text{P}}_{2}[*k,1]\subseteq\Sigma^{\text{P}}_{2}[* k,2]\subseteq\cdots\subseteq\Sigma^{\text{P}}_{2}[*k,\text{SAT}]\subseteq\Sigma^{ \text{P}}_{2}[*k,\text{P}].\end{array} \)  
(See also Figure 1 for a visual overview of these inclusion relations.)