# A Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy
## 2 Preliminaries  
### Computational Complexity  
We assume that the reader is familiar with basic notions from the theory of computational complexity, such as the complexity classes P and NP. For more details, we refer to textbooks on the topic (see, e.g., [11,12]). There are many natural decision problems that are not contained in the classical complexity classes P and NP (under some common complexity-theoretic assumptions). The _Polynomial Hierarchy_[2,3,12,13] contains a hierarchy of increasing complexity classes \(\Sigma^{\mathrm{P}}_{i}\), for all \(i\geq 0\). We give a characterization of these classes based on the satisfiability problem of various classes of quantified Boolean formulas. A _quantified Boolean formula_ is a formula of the form \(Q_{1}X_{1}Q_{2}X_{2}\dots Q_{m}X_{m}\psi\), where each \(Q_{i}\) is either \(\forall\) or \(\exists\), the \(X_{i}\) are disjoint sets of propositional variables, and \(\psi\) is a Boolean formula over the variables in \(\bigcup_{i=1}^{m}X_{i}\). The quantifier-free part of such formulas is called the _matrix_ of the formula. Truth of such formulas is defined in the usual way. Let \(\gamma=\{x_{1}\mapsto d_{1},\ldots,x_{n}\mapsto d_{n}\}\) be a function that maps some variables of a formula \(\varphi\) to other variables or to truth values. We let \(\varphi[\gamma]\) denote the application of such a substitution \(\gamma\) to the formula \(\varphi\). We also write \(\varphi[x_{1}\mapsto d_{1},\ldots,x_{n}\mapsto d_{n}]\) to denote \(\varphi[\gamma]\). For each \(i\geq 1\), the decision problem QSAT\({}_{i}\) is defined as follows. \(\underline{\text{QSAT}_{i}}\)  
_Instance:_ A quantified Boolean formula \(\varphi=\exists X_{1}\forall X_{2}\exists X_{3}\ldots Q_{i}X_{i}\psi\), where \(Q_{i}\) is a universal quantifier if \(i\) is even and an existential quantifier if \(i\) is odd. _Question:_ Is \(\varphi\) true? Input formulas to the problem QSAT\({}_{i}\) are called \(\Sigma_{i}^{\text{P}}\)-formulas. For each nonnegative integer \(i\geq 0\), the complexity class \(\Sigma_{i}^{\text{P}}\) can be characterized as the closure of the problem QSAT\({}_{i}\) under polynomial-time reductions [2; 3]--that is, all decision problems that are polynomial-time reducible to QSAT\({}_{i}\). The \(\Sigma_{i}^{\text{P}}\)-hardness of QSAT\({}_{i}\) holds already when the matrix of the input formula is restricted to 3 CNF for odd \(i\), and restricted to 3 DNF for even \(i\). Note that the class \(\Sigma_{0}^{\text{P}}\) coincides with P, and the class \(\Sigma_{1}^{\text{P}}\) coincides with NP. For each \(i\geq 1\), the class \(\Pi_{i}^{\text{P}}\) is defined as co-\(\Sigma_{i}^{\text{P}}\)--that is, \(\Pi_{i}^{\text{P}}=\{\,\{0,1\}^{*}\setminus L:L\in\Sigma_{i}^{\text{P}}\,\}\). The classes \(\Sigma_{i}^{\text{P}}\) and \(\Pi_{i}^{\text{P}}\) can also be defined by means of nondeterministic Turing machines with an oracle. Intuitively, oracles are black-box machines that can solve a problem in a single time step--for more details, see, e.g., Chapter 3 of [11]. For any complexity class \(C\), we let NP\({}^{\text{C}}\) be the set of decision problems that are decided in polynomial time by a nondeterministic Turing machine with an oracle for a problem that is in the class \(C\). Then, the classes \(\Sigma_{i}^{\text{P}}\) and \(\Pi_{i}^{\text{P}}\), for \(i\geq 0\), can be equivalently defined by letting \(\Sigma_{0}^{\text{P}}=\Pi_{0}^{\text{P}}=\text{P}\), and for each \(i\geq 1\) letting \(\Sigma_{i}^{\text{P}}=\text{NP}^{\Sigma_{i-1}^{\text{P}}}\) and \(\Pi_{i}^{\text{P}}=\text{co-NP}^{\Sigma_{i-1}^{\text{P}}}\). The Polynomial Hierarchy also includes complexity classes between \(\Sigma_{i}^{\text{P}}\) and \(\Sigma_{i+1}^{\text{P}}\)--such as the classes \(\Delta_{i+1}^{\text{P}}\) and \(\Theta_{i+1}^{\text{P}}\). The class \(\Delta_{i+1}^{\text{P}}\) consists of all decision problems that are decided in polynomial time by a deterministic Turing machine with an oracle for a problem that is in the class \(\Sigma_{i}^{\text{P}}\).