# A Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy
## 4 Knowledge Representation and Reasoning Problems  
### Disjunctive Answer Set Programming  
The following problems from the setting of disjunctive answer set programming (ASP) are based on the notions of disjunctive logic programs and answer sets for such programs (cf. [48; 49]). A _disjunctive logic program_\(P\) is a finite set of rules of the form \(r=(a_{1}\vee\dots\lor a_{k}\gets b_{1},\dots,b_{m},\)_not_\(c_{1},\dots,not\)\(c_{n})\), for \(k,m,n\geq 0\), where all \(a_{i}\), \(b_{j}\) and \(c_{l}\) are atoms. For each such rule, \(a_{1}\vee\dots\lor a_{k}\) is called the _head_ of the rule, and \(b_{1},\dots,b_{m},not\)\(c_{1},\dots,not\)\(c_{n}\) is called the _body_ of the rule. A rule is called _disjunctive_ if \(k>1\), and it is called _normal_ if \(k\leq 1\) (note that we only call rules with strictly more than one disjunct in the head disjunctive). A rule is called _dual-normal_ if \(m\leq 1\). A program is called normal if all its rules are normal, it is called negation-free if all its rules are negation-free, and it is called dual-normal if all its rules are dual-normal. We let \(\operatorname{At}(P)\) denote the set of all atoms occurring in \(P\). By _literals_, we mean atoms \(a\) or their negations _not_\(a\). The _(Gelfand-Lifschitz) reduct_ of a program \(P\) with respect to a set \(M\) of atoms, denoted \(P^{M}\), is the program obtained from \(P\) by: (i) removing rules with _not_\(a\) in the body, for each \(a\in M\), and (ii) removing literals _not_\(a\) from all other rules [50]. An _answer set_\(A\) of a program \(P\) is a subset-minimal model of the reduct \(P^{A}\). One important decision problem is to decide, given a disjunctive logic program \(P\), whether \(P\) has an answer set. We consider various parameterizations of this problem. Two of these are related to atoms that must be part of any answer set of a program \(P\). We identify a subset \(\operatorname{Comp}(P)\) of _compulsory atoms_, that any answer set must include. Given a program \(P\), we let \(\operatorname{Comp}(P)\) be the smallest set such that: (i) if \((w\gets not\ w)\) is a rule of \(P\), then \(w\in\operatorname{Comp}(P)\); and (ii) if \((b\gets a_{1},\dots,a_{n})\) is a rule of \(P\), and \(a_{1},\dots,a_{n}\in\operatorname{Comp}(P)\), then \(b\in\operatorname{Comp}(P)\). We then let the set \(\operatorname{Cont}(P)\) of _contingent atoms_ be those atoms that occur in \(P\) but are not in \(\operatorname{Comp}(P)\). We call a rule _contingent_ if all the atoms that appear in the head are contingent. Another of the parameterizations that we consider is based on the notion of backdoors to normality for disjunctive logic programs. A set \(B\) of atoms is a _normality-backdoor_ for a program \(P\) if deleting the atoms \(b\in B\) from the rules of \(P\) results in a normal program. Deciding if a program \(P\) has a normality-backdoor of size at most \(k\) can be decided in fixed-parameter tractable time [29]. ASP-consistency(#cont.atoms)  
_Instance:_ A disjunctive logic program \(P\). _Parameter:_ The number of contingent atoms of \(P\). _Question:_ Does \(P\) have an answer set? **Complexity:** para-co-NP-complete [7; 30]. ```
``` ASP-consistency(\(\#\)cont.rules)  
_Instance:_ A disjunctive logic program \(P\). _Parameter:_ The number of contingent rules of \(P\). _Question:_ Does \(P\) have an answer set? ```

```
ASP-consistency(\(\#\)disj.rules)  
_Instance:_ A disjunctive logic program \(P\). _Parameter:_ The number of disjunctive rules of \(P\). _Question:_ Does \(P\) have an answer set? ```

```
ASP-consistency(\(\#\)dual-normal.rules)  
_Instance:_ A disjunctive logic program \(P\). _Parameter:_ The number of rules of \(P\) that are dual-normal. _Question:_ Does \(P\) have an answer set? ```

```
ASP-consistency(str.norm.bd-size)  
_Instance:_ A disjunctive logic program \(P\). _Parameter:_ The size of the smallest normality-backdoor for \(P\). _Question:_ Does \(P\) have an answer set? ```

```
ASP-consistency(max.atom.occ.) _Instance:_ A disjunctive logic program \(P\).