# A Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy
## 4 Knowledge Representation and Reasoning Problems
### Disjunctive Answer Set Programming
For all \(v\in V\), \(t[v]=\mathsf{eff}(a)[v]\) if \(\mathsf{eff}(a)[v]\
eq\mathbf{u}\) and \(t[v]=s[v]\) otherwise. Let \(s_{0},s_{\ell}\in D^{n}\) and let \(\omega=(a_{1},\ldots,a_{\ell})\) be a sequence of actions (of length \(\ell\)). We say that \(\omega\) is a _plan from \(s_{0}\) to \(s_{\ell}\)_ if either (i) \(\omega\) is the empty sequence (and \(\ell=0\), and thus \(s_{0}=s_{\ell}\)), or (ii) there are states \(s_{1},\ldots,s_{\ell-1}\in D^{n}\) such that for each \(i\in[\ell]\), \(a_{i}\) is valid in \(s_{i-1}\) and \(s_{i}\) is the result of \(a_{i}\) in \(s_{i-1}\). A state \(s\in D^{n}\) is a _goal state_ if for all \(v\in V\), either \(G[v]=s[v]\) or \(G[v]=\mathbf{u}\). An action sequence \(\omega\) is a _plan for \(\mathbb{P}\)_ if \(\omega\) is a plan from \(I\) to a goal state. We also allow actions to have _conditional effects_ (see, e.g., ([PERSON], 2016)). A conditional effect is of the form \(s\triangleright t\), where \(s,t\in(D^{+})^{n}\) are partial states. Intuitively, such a conditional effect ensures that the variable assignment \(t\) is only applied if the condition \(s\) is satisfied. When allowing conditional effects, the effect of an action is not a partial state \(\mathsf{eff}(a)\in(D^{+})^{n}\), but a set \(\mathsf{eff}(a)=\{s_{1}\triangleright t_{1},\ldots,s_{\ell}\triangleright t_{ \ell}\}\) of conditional effects. (For the sake of simplicity, we assume that the partial states \(t_{1},\ldots,t_{\ell}\) are non-conflicting--that is, there exist no \(v\in V\) and no \(i_{1},i_{2}\in[\ell]\) with \(i_{1}<i_{2}\) such that \(\mathbf{u}\
eq t_{i_{1}}[v]\
eq t_{i_{2}}[v]\
eq\mathbf{u}\).) The result of an action \(a\) with \(\mathsf{eff}(a)=\{s_{1}\triangleright t_{1},\ldots,s_{\ell}\triangleright t_{\ell}\}\) in a state \(s\) (in which \(a\) is valid) is the state \(t\in D^{n}\) that is defined as follows. For all \(v\in V\), \(t[v]=t_{i}[v]\)Bounded-Uncertain-Planning

_Instance:_ an uncertain planning instance \(\mathbb{P}=(V,V_{u},D,A,I,G)\), and an integer \(k\). _Parameter:_\(k\). _Question:_ Is there a plan of length \(k\) for \(\mathbb{P}\) that works for each complete initial state \(I_{0}\) that extends \(I\)? **Complexity:**\(\Sigma_{2}^{\mathbb{P}}[k*]\)-complete [7; 39]. Polynomial-Planning(bounded-deviation)

_Instance:_ an uncertain planning instance \(\mathbb{P}=(V,V_{u},D,A,I,G)\), an integer \(d\), and an integer \(u\) given in unary. _Parameter:_\(d\). _Question:_ Is there a plan for \(\mathbb{P}\) of length \(\leq u\) that works for each complete initial state \(I_{0}\) that extends \(I\) and for which at most \(d\) unknown variables deviate from the base value? **Complexity:**\(\Sigma_{2}^{\mathbb{P}}[*k,\mathbb{P}]\)-complete [7; 39]. ### Turing Machine Halting

The following problems are related to alternating Turing machines (ATMs), possibly with multiple tapes. ATMs are nondeterministic Turing machines where the states are divided into existential and universal states, and where each configuration of the machine is called existential or universal according to the state that the machine is in. A run \(\rho\) of the ATM \(\mathbb{M}\) on an input \(x\) is a tree whose nodes correspond to configurations of \(\mathbb{M}\) in such a way that (1) for each non-root node \(v\) of the tree with parent node \(v^{\prime}\), the machine \(\mathbb{M}\) can transition from the configuration corresponding to \(v^{\prime}\) to the configuration corresponding to \(v\), (2) the root node corresponds to the initial configuration of \(\mathbb{M}\), and (3) each leaf node corresponds to a halting configuration. A computation path in a run of \(\mathbb{M}\) is a root-to-leaf path in the run. Moreover, the nodes of a run \(\rho\) are labelled accepting or rejecting, according to the following definition. A leaf of \(\rho\) is labelled accepting if the configuration corresponding to it is an accepting configuration, and the leaf is labelled rejecting if it is a rejecting configuration.