# A Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy
## 4 Knowledge Representation and Reasoning Problems
### Disjunctive Answer Set Programming
A variable \(x\in\mathrm{Var}(\Phi)\) is connected by an edge with a clause \(c\) of the formula \(\varphi_{i}\in\Phi\) if \(x\) occurs in \(c\), i.e., \(x\in\mathrm{Var}(c)\). Consider the following parameterizations of the problem Maj-Agenda-Safety(f-tw)

_Instance:_ an agenda \(\Phi\) containing only CNF formulas. _Parameter:_ The treewidth of the formula primal graph of \(\Phi\). _Question:_ Is \(\Phi\) safe for the majority rule? **Complexity:** fixed-parameter tractable [7; 37]. Maj-Agenda-Safety(f-tw*)

_Instance:_ an agenda \(\Phi\) containing only CNF formulas. _Parameter:_ The treewidth of the formula incidence graph of \(\Phi\). _Question:_ Is \(\Phi\) safe for the majority rule? **Complexity:** para-\(\Pi^{\mathrm{P}}_{2}\)-complete [7; 37]. Maj-Agenda-Safety(c-tw)

_Instance:_ an agenda \(\Phi\) containing only CNF formulas. _Parameter:_ The treewidth of the clausal primed graph of \(\Phi\). _Question:_ Is \(\Phi\) safe for the majority rule? **Complexity:** para-co-NP-complete [7; 37]. ### Planning

The following parameterized problems are related to planning in the face of uncertainty. We begin by describing the framework of SAS\({}^{+}\) planning (see, e.g., ([PERSON], 2016)). Let \(V=\{v_{1},\ldots,v_{n}\}\) be a finite set of _variables_ over a finite _domain_\(D\). Furthermore, let \(D^{+}=D\cup\{\mathbf{u}\}\), where \(\mathbf{u}\) is a special _undefined_ value not present in \(D\). Then \(D^{n}\) is the set of _total states_ and \((D^{+})^{n}\) is the set of _partial states_ over \(V\) and \(D\). Intuitively, a state \((d_{1},\ldots,d_{n})\in D^{n}\) corresponds to an assignment that assigns to each variable \(v_{i}\in V\) the value \(d_{i}\in D\), and a partial state corresponds to a partial assignment that assigns a value to some variables \(v_{i}\in V\). Clearly, \(D^{n}\subseteq(D^{+})^{n}\)--that is, each total state is also a partial state. Let \((d_{1},\ldots,d_{n})=s\in(D^{+})^{n}\) be a state. Then, the value of a variable \(v_{i}\) in state \(s\) is denoted by \(s[v_{i}]=d_{i}\). An _SAS\({}^{+}\) instance_ is a tuple \(\mathbb{P}=(V,D,A,I,G)\), where \(V\) is a set of variables, \(D\) is a domain, \(A\) is a set of _actions_, \(I\in D^{n}\) is the _initial state_ and \(G\in(D^{+})^{n}\) is the (partial) _goal state_. Each action \(a\in A\) has a _precondition_\(\mathsf{pre}(a)\in(D^{+})^{n}\) and an _effect_\(\mathsf{eff}(a)\in(D^{+})^{n}\). We will frequently use the convention that a variable has the value \(\mathbf{u}\) in a precondition/effect unless a value is explicitly specified. Furthermore, by a slight abuse of notation, we denote actions and partial states such as preconditions, effects, and goals as follows. Let \(a\in A\) be an action, and let \(\{p_{1},\ldots,p_{m}\}\subseteq V\) be the set of variables that are not assigned by \(\mathsf{pre}(a)\) to the value \(\mathbf{u}\)--that is, \(\{v\in V:\mathsf{pre}(a)[v]\
eq\mathbf{u}\}=\{p_{1},\ldots,p_{m}\}\). Moreover, suppose that \(\mathsf{pre}(a)[p_{1}]=d_{1},\ldots,\mathsf{pre}(a)[p_{m}]=d_{m}\). Then, we denote the precondition \(\mathsf{pre}(a)\) by \(\mathsf{pre}(a)=\{p_{1}\mapsto d_{1},\ldots,p_{m}\mapsto d_{m}\}\). In particular, if \(\mathsf{pre}(a)\) is the partial state such that \(\mathsf{pre}(a)[v]=\mathbf{u}\) for each \(v\in V\), we denote \(\mathsf{pre}(a)\) by \(\emptyset\). We use a similar notation for effects. Let \(a\) be the action with \(\mathsf{pre}(a)=\{p_{1}\mapsto d_{1},\ldots,p_{m}\mapsto d_{m}\}\) and \(\mathsf{eff}(a)=\{e_{1}\mapsto d_{1}^{\prime},\ldots,e_{\ell}\mapsto d_{\ell}^ {\prime}\}\). We then use the notation \(a:\{p_{1}\mapsto d_{1},\ldots,p_{m}\mapsto d_{m}\}\to\{e_{1}\mapsto d_{1}^{ \prime},\ldots,e_{m^{\prime}}\mapsto d_{m^{\prime}}^{\prime}\}\) to describe the action \(a\). Let \(a\in A\) be an action and \(s\in D^{n}\) be a state. Then, \(a\) is _valid in \(s\)_ if for all \(v\in V\), either \(\mathsf{pre}(a)[v]=s[v]\) or \(\mathsf{pre}(a)[v]=\mathbf{u}\). The _result of \(a\) in \(s\)_ is the state \(t\in D^{n}\) defined as follows.