# A Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy
## 4 Knowledge Representation and Reasoning Problems
### Disjunctive Answer Set Programming
For instance, the majority rule \(F^{\mathrm{maj}}\) is complete, whenever the number \(n\) of individuals is odd. An agenda \(\Phi\) is _safe_ with respect to an aggregation procedure \(F\), if \(F\) is consistent when applied to profiles of judgment sets over \(\Phi\). We say that an agenda \(\Phi\) satisfies the _median property (MP)_ if every inconsistent subset of \(\Phi\) has itself an inconsistent subset of size at most 2. Safety for the majority rule can be characterized in terms of the median property as follows: an agenda \(\Phi\) is safe for the majority rule if and only if \(\Phi\) satisfies the MP [57; 58]. The problem of deciding whether an agenda satisfies the MP is \(\Pi^{\mathrm{P}}_{2}\)-complete [57]. Maj-Agenda-Safety(formula size)

_Instance:_ an agenda \(\Phi\). _Parameter:_\(\ell=\max\{\,|\,\varphi|:\varphi\in\Phi\,\}\). _Question:_ Is \(\Phi\) safe for the majority rule? **Complexity:** para-\(\Pi^{\mathrm{P}}_{2}\)-complete [7; 37]. Maj-Agenda-Safety(degree)

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

_Instance:_ an agenda \(\Phi\) containing only CNF formulas, where \(\ell=\max\{\,|\,\varphi|:\varphi\in B(\Phi)\,\}\), and where \(d\) is the degree of \(\Phi\). _Parameter:_\(\ell+d\). _Question:_ Is \(\Phi\) safe for the majority rule? **Complexity:** para-\(\Pi^{\mathrm{P}}_{2}\)-complete [7; 37]. The above three parameterized problems remain para-\(\Pi^{\mathrm{P}}_{2}\)-hard even when restricted to agendas based on formulas that are Horn formulas containing only clauses of size at most 2 [7; 37]. Maj-Agenda-Safety(agenda size)

_Instance:_ an agenda \(\Phi\). _Parameter:_\(|\Phi|\). _Question:_ Is \(\Phi\) safe for the majority rule? **Complexity:** FPTNP[few]-complete [7; 37]. Moreover, the following upper and lower bounds on the number of oracle queries are known for the above problem. Maj-Agenda-Safety(agenda size) can be decided in fpt-time using \(2^{O(k)}\) queries to an NP oracle, where \(k=|\Phi|\)[7; 37]. In addition, there is no fpt-algorithm that decides Maj-Agenda-Safety(agenda size) using \(o(\log k)\) queries to an NP oracle, unless the PolynomialHierarchy collapses [7; 37]. Maj-Agenda-Safety(counterexample size)

_Instance:_ an agenda \(\Phi\), and an integer \(k\). _Parameter:_\(k\). _Question:_ Does every inconsistent subset \(\Phi^{\prime}\) of \(\Phi\) of size \(k\) have itself an inconsistent subset of size at most 2? **Complexity:**\(\Pi^{\mathrm{P}}_{2}[k*]\)-hard [7; 37]. Let \(\Phi=\{\varphi_{1},\ldots,\varphi_{m},\
eg\varphi_{1},\ldots,\
eg\varphi_{m}\}\) be an agenda, where each \(\varphi_{i}\) is a CNF formula. We define the following graphs that are intended to capture the interaction between formulas in \(\Phi\). The _formula primal graph_ of \(\Phi\) has as vertices the variables \(\mathrm{Var}(\Phi)\) occurring in the agenda, and two variables are connected by an edge if there exists a formula \(\varphi_{i}\) in which they both occur. The _formula incidence graph_ of \(\Phi\) is a bipartite graph whose vertices consist of (1) the variables \(\mathrm{Var}(\Phi)\) occurring in the agenda and (2) the formulas \(\varphi_{i}\in\Phi\). A variable \(x\in\mathrm{Var}(\Phi)\) is connected by an edge with a formula \(\varphi_{i}\in\Phi\) if \(x\) occurs in \(\varphi_{i}\), i.e., \(x\in\mathrm{Var}(\varphi_{i})\). The _clausal primal graph_ of \(\Phi\) has as vertices the variables \(\mathrm{Var}(\Phi)\) occurring in the agenda, and two variables are connected by an edge if there exists a formula \(\varphi_{i}\) and a clause \(c\in\varphi_{i}\) in which they both occur. The _clausal incidence graph_ of \(\Phi\) is a bipartite graph whose vertices consist of (1) the variables \(\mathrm{Var}(\Phi)\) occurring in the agenda and (2) the clauses \(c\) occurring in formulas \(\varphi_{i}\in\Phi\).