# A Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy
## 4 Knowledge Representation and Reasoning Problems
### Disjunctive Answer Set Programming
A non-leaf node of \(\rho\) that corresponds to an existential configuration is labelled accepting if at least one of its children is labelled accepting. A non-leaf node of \(\rho\) that corresponds to a universal configuration is labelled accepting if all of its children are labelled accepting. An ATM \(\mathbb{M}\) is 2-alternating if for each input \(x\), each computation path in the run of \(\mathbb{M}\) on input \(x\) switches at most once from an existential configuration to a universal configuration, or vice versa. For more details on the terminology, we refer to the work of [PERSON] and [PERSON] [8; 41] and to the work of [PERSON] and [PERSON]--Appendix A.1 in [22]. We consider the following restrictions on ATMs. An \(\exists\forall\)_-Turing machine_ (or simply \(\exists\forall\)-machine) is a 2-alternating ATM, where the initial state is an existential state. Let \(\ell,t\geq 1\) be positive integers. We say that an \(\exists\forall\)-machine \(\mathbb{M}\)_halts (on the empty string) with existential cost \(\ell\) and universal cost \(t\)_ if: (1) there is an accepting run of \(\mathbb{M}\) with the empty input \(\epsilon\), and (2) each computation path of \(\mathbb{M}\) contains at most \(\ell\) existential configurations and at most \(t\) universal configurations. The following problem, where the number of Turing machine tapes is given as part of the input, is \(\Sigma_{2}^{\mathbb{P}}[k*]\)-complete. \(\Sigma_{2}^{\mathbb{P}}[k*]\)-TM-halt\({}^{*}\). _Instance:_ Positive integers \(m,k,t\geq 1\), and an \(\exists\forall\)-machine \(\mathbb{M}\) with \(m\) tapes. _Parameter:_\(k\). _Question:_ Does \(\mathbb{M}\) halt on the empty string with existential cost \(k\) and universal cost \(t\)? **Complexity:**\(\Sigma_{2}^{\mathbb{P}}[k*]\)-complete [7; 8]. Let \(m\geq 1\) be a constant integer. Then, the following parameterized decision problem, where the number of Turing machine tapes is fixed, is also \(\Sigma_{2}^{\mathbb{P}}[k*]\)-complete. \(\Sigma^{\mathrm{P}}_{2}[k*]\)-TM-halt\({}^{m}\). _Instance:_ Positive integers \(k,t\geq 1\), and an \(\exists\forall\)-machine \(\mathbb{M}\) with \(m\) tapes. _Parameter:_\(k\). _Question:_ Does \(\mathbb{M}\) halt on the empty string with existential cost \(k\) and universal cost \(t\)? **Complexity:**\(\Sigma^{\mathrm{P}}_{2}[k*]\)-complete [7; 8]. In addition, the parameterized complexity class \(\Sigma^{\mathrm{P}}_{2}[k*]\) can also be characterized by means of alternating Turing machines in the following way. Let \(P\) be a parameterized problem. An \(\Sigma^{\mathrm{P}}_{2}[k*]\)_-machine for \(P\)_ is a \(\exists\forall\)-machine \(\mathbb{M}\) such that there exists a computable function \(f\) and a polynomial \(p\) such that: (1) \(\mathbb{M}\) decides \(P\) in time \(f(k)\cdot p(|x|)\); and (2) for all instances \((x,k)\) of \(P\) and each computation path \(R\) of \(\mathbb{M}\) with input \((x,k)\), at most \(f(k)\cdot\log|x|\) of the existential configurations of \(R\) are nondeterministic. We say that a parameterized problem \(P\)_is decided by some \(\Sigma^{\mathrm{P}}_{2}[k*]\)-machine_ if there exists a \(\Sigma^{\mathrm{P}}_{2}[k*]\)-machine for \(P\). Then, \(\Sigma^{\mathrm{P}}_{2}[k*]\) is exactly the class of parameterized decision problems that are decided by some \(\Sigma^{\mathrm{P}}_{2}[k*]\)-machine [7; 8]. ## 7 Conclusions

In this paper, we provided a list of parameterized problems that are based on problems at higher levels of the Polynomial Hierarchy, together with a complexity classification indicating whether they allow a (many-to-one or Turing) fpt-reduction to SAT or not. These complexity classifications are based in part on recently developed parameterized complexity classes--e.g., \(\Sigma^{\mathrm{P}}_{2}[k*]\) and \(\Sigma^{\mathrm{P}}_{2}[*k,\mathrm{P}]\)[7; 8], FPTNP[few] [6; 7] and PH[level] [7; 36].