# 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
Dual to the classical complexity class \(\Sigma^{\text{P}}_{2}\) is its co-class \(\Pi^{\text{P}}_{2}\), whose canonical complete problem is complementary to the problem \(\mathsf{QSat}_{2}\). Similarly, we can define dual classes for the \(k\)-\(*\) class and for each of the parameterized complexity classes in the \(*\)-\(k\) hierarchy. These co-classes are based on problems complementary to the problems \(\Sigma^{\text{P}}_{2}[k*]\text{-}\mathsf{WSat}\) and \(\Sigma^{\text{P}}_{2}[*k]\text{-}\mathsf{WSat}\)--i.e., these problems have as yes-instances exactly the no-instances of \(\Sigma^{\text{P}}_{2}[k*]\text{-}\mathsf{WSat}\) and \(\Sigma^{\text{P}}_{2}[*k]\text{-}\mathsf{WSat}\), respectively. Equivalently, these complementary problems can be considered as variants of \(\Sigma^{\text{P}}_{2}[k*]\text{-}\mathsf{WSat}\) and \(\Sigma^{\text{P}}_{2}[*k]\text{-}\mathsf{WSat}\) where the existential and universal quantifiers are swapped, and are therefore denoted with \(\Pi^{\text{P}}_{2}[k*]\text{-}\mathsf{WSat}\) and \(\Pi^{\text{P}}_{2}[*k]\text{-}\mathsf{WSat}\). We use a similar notation for the dual complexity classes, e.g., we denote \(\text{co-}\Sigma^{\text{P}}_{2}[*k,t]\) by \(\Pi^{\text{P}}_{2}[*k,t]\). The class \(\Sigma^{\text{P}}_{2}[k*]\) includes the class para-co-NP as a subset, and is contained in the class Xco-NP as a subset. Similarly, each of the classes \(\Sigma^{\text{P}}_{2}[*k,t]\) include the the class para-NP as a subset, and is contained in the class XNP. Under some common complexity-theoretic assumptions, the class \(\Sigma^{\text{P}}_{2}[k*]\) can be separated from para-NP on the one hand, and para-\(\Sigma^{\text{P}}_{2}\) on the other hand. In particular, assuming that \(\text{NP}\
eq\text{co-NP}\), it holds that \(\Sigma^{\text{P}}_{2}[k*]\
ot\subseteq\text{para-NP}\), that para-\(\text{NP}\
ot\subseteq\Sigma^{\text{P}}_{2}[k*]\) and that \(\Sigma^{\text{P}}_{2}[k*]\subset\text{para-}\Sigma^{\text{P}}_{2}\)[7; 8]. Similarly, the classes \(\Sigma^{\text{P}}_{2}[*k,t]\) can be separated from para-co-NP and para-\(\Sigma^{\text{P}}_{2}\). Assuming that \(\text{NP}\
eq\text{co-NP}\), it holds that \(\Sigma^{\text{P}}_{2}[*k,1]\
ot\subseteq\text{para-co-NP}\), that para-co-\(\text{NP}\
ot\subseteq\Sigma^{\text{P}}_{2}[*k,\text{P}]\) and thus in particular that para-co-\(\text{NP}\
ot\subseteq\Sigma^{\text{P}}_{2}[*k,1]\), and that \(\Sigma^{\text{P}}_{2}[*k,\text{P}]\subsetneq\text{para-}\Sigma^{\text{P}}_{2}\)[7; 8]. One can also enhance the power of polynomial-time SAT encodings by considering polynomial-time algorithms that can query a SAT solver multiple times--that is, polynomial-time Turing reductions. Such an approach has been shown to be quite effective in practice (see, e.g., [33; 34; 35]) and extends the scope of SAT solvers to problems in the class \(\Delta^{\text{P}}_{2}\), but not to problems that are \(\Sigma^{\text{P}}_{2}\)-hard or \(\Pi^{\text{P}}_{2}\)-hard. In addition, here, switching from polynomial-time to fpt-time provides a significant increase in power. The class para-\(\Delta^{\text{P}}_{2}\) contains all parameterized problems that can be decided by an fpt-algorithm that can query a SAT oracle multiple times--i.e., by an fpt-time Turing reduction to SAT. (One can prove this by following the proof of Theorem 4 in [24] that \(\text{FPT}=\text{para-P}\), with the modification that the algorithms are given access to a SAT oracle.) In addition, one could restrict the number of queries that the algorithm is allowed to make. The class para-\(\Theta^{\mathrm{P}}_{2}\) consists of all parameterized problems that can be decided by an fpt-algorithm that can query a SAT oracle at most \(f(k)\log n\) many times, where \(k\) is the parameter value, \(n\) is the input size, and \(f\) is some computable function. (This statement one can prove by following the proof of Theorem 4 in [24] that \(\mathrm{FPT}=\) para-P, with the modification that the algorithms can query a SAT oracle an amount of times that depends logarithmically on the input size.)