## 2 Preliminaries
### Answer Set Programming (ASP)
#### 2.2.2 Semantics  
A set \(M\subseteq\text{at}(P)\)_satisfies_ a rule \(r\) if (i) \((H_{r}\cup B_{r}^{-})\cap M\
eq\emptyset\) or \(B_{r}^{+}\
ot\subseteq M\) for \(r\in\text{DISJ}(P)\) or (ii) \(r\in\text{CH}(P)\cup\text{OPT}(P)\). Hence, choice and optimization rules are always satisfied. \(M\) is a model of \(P\), denoted by \(M\vDash P\), if \(M\) satisfies every rule \(r\in P\). The _reduct_\(r^{M}\) (i) of a choice rule \(r\) is the set \(\{a\gets B_{r}^{+}\mid a\in H_{r}\cap M,B_{r}^{-}\cap M=\emptyset\}\) of rules, and (ii) of a disjunctive rule \(r\) is the singleton \(\{H_{r}\gets B_{r}^{+}\mid B_{r}^{-}\cap M=\emptyset\}\). \(P^{M}:=\bigcup_{r\in P}r^{M}\) is called _GL reduct_ of \(P\) with respect to \(M\). A set \(M\subseteq\text{at}(P)\) is an _answer set_ of \(P\) if (i) \(M\vDash P\) and (ii) there is no \(M^{\prime}\subsetneq M\) such that \(M^{\prime}\vDash P^{M}\), that is, \(M\) is _subset minimal with respect to \(P^{M}\)_. We call \(\text{cst}(P,M):=\left|\{r\in P,r\text{ is an optimization rule},(B_{r}^{+}\cap M)\cup(B_{r}^{-}\setminus M)\
eq \emptyset\}\right|\) the _cost_ of answer set \(M\) for \(P\). An answer set \(M\) of \(P\) is _optimal_ if its cost is minimal over all answer sets. Intuitively, a choice rule of the form \(\{a_{1};\ldots;a_{\ell}\}\leftarrow\ a_{\ell+1},\ldots,a_{m},\
eg a_{m+1}, \ldots,\
eg a_{n}\) allows us to conclude that if all atoms \(a_{\ell+1},\ldots,a_{m}\) are in an answer set \(M\) and there is no evidence that any atom of \(a_{m+1},\ldots,a_{n}\) is in \(M\) (so subset-minimality with respect to the reduct forces that \(a_{m+1},\ldots,a_{n}\
ot\in M\)), we can conclude that any subset of the atoms \(a_{1},\ldots,a_{\ell}\) can be in \(M\). In other words, the atoms \(a_{1},\ldots,a_{\ell}\) are \"excluded\" from subset minimization. A disjunctive rule of the form \(a_{1}\vee\cdots\lor a_{\ell}\leftarrow\ a_{\ell+1},\ldots,a_{m},\
eg a_{m+1}, \ldots,\
eg a_{n}\) allows us to conclude that if all atoms \(a_{\ell+1},\ldots,a_{m}\) are in \(M\) and there is no evidence that any atom of \(a_{m+1},\ldots,a_{n}\) is in \(M\), we can conclude that a subset of the atoms \(a_{1},\ldots,a_{\ell}\) can be in \(M\), however, remains subject to subset minimization with respect to the reduct. The meaning of optimization rules is simply that we minimize the cardinality of a set \(M\) of atoms with respect to the literals in \(M\) that occur in any minimization rule positively and not in \(M\) for those that occur in any minimization rules negatively. **Example 1**. : _Consider program_  
\[P=\{\overbrace{\{e_{ab}\}}^{r_{eb}};\overbrace{\{e_{bc}\}}^{r_{bc}};\overbrace {\{e_{cd}\}}^{r_{cd}};\overbrace{\{e_{ad}\}}^{r_{cd}};\overbrace{\{e_{ad}\}} ^{r_{cd}};\overbrace{\{e_{ad}\}}^{r_{ab}};\overbrace{a_{b}\leftarrow{e_{ab} \}}^{r_{b}};\overbrace{a_{d}\leftarrow{e_{ad}}}^{r_{d}};\overbrace{a_{c} \leftarrow{a_{b},e_{bc}}}^{r_{c1}};\overbrace{a_{c}\leftarrow{a_{d},e_{cd}}}^ {r_{c2}};\overbrace{a_{c}\leftarrow{a_{d},e_{cd}}}^{r_{c2}};\overbrace{a_{c} \leftarrow{a_{c}}}^{r_{c}}\}.\]  
_The set \(A=\{e_{ab},e_{bc},a_{b},a_{c}\}\) is an answer set of \(P\), since \(\{e_{ab},e_{bc},a_{b},a_{c}\}\) is the only minimal model of \(P^{A}=\{e_{ab}\leftarrow;\,e_{bc}\leftarrow;\,a_{b}\leftarrow{e_{ab}};\,a_{d} \gets e_{ad};\,a_{c}\leftarrow{a_{b},e_{bc}};\,a_{c}\leftarrow{a_{d},e_{ cd}}\}\). Then, consider program \(R=\{a\lor c\gets b;\ b\gets c,\
eg g;\ c\gets a;\ b\lor c \gets e;\ h\lor i\gets g,\
eg c;\ a\lor b;\ g\leftarrow\
eg i;\ c;\ \{d\} \gets g\}\). The set \(B=\{b,c,d,g\}\) is an answer set of \(R\) since \(\{b,c,d,g\}\) and \(\{a,c,d,g\}\) are the minimal models of \(R^{B}=\{a\lor c\gets b;\ c\gets a;\ b\lor c\gets e;\ a\lor b;\ g;\ c;\ d \gets g\}\)._  
In this paper, we mainly consider the output answer set problem, that is, output an answer set for an ASP program. The decision version of this problem is \(\Sigma_{2}^{p}\)-complete.