On the Computational Complexity of Naive-Based Semantics for Abstract Dialectical Frameworks

1 Introduction

Over the last decade, argumentation theory emerged as one of the major fields in artificial intelligence and non-monotonic reasoning. There, abstract argumentation frameworks (AFs) as introduced by Dung [1995] became a key formalism with applications to a variety of non-monotonic reasoning problems such as logic programming, inconsistency handling, legal reasoning and many others [Rahwan et al., 2009].

The basic Dung-style framework only consists of a set of abstract arguments and a binary relation between them, denoted as attacks. The evaluation of such an AF is then based on model-theoretic semantics, which allow to select sets of arguments that can "stand together". The need to represent more complex relations between the abstract entities led to a wide range of extensions, which allow to handle preferences and values on arguments [Amgoud and Cayrol, 2002; Bench-Capon, 2003], weights [Dunne et al., 2011], probabilities [Li et al., 2011] and introduce a positive relation between arguments, so-called supports [Amgoud et al., 2008]. Recently, abstract dialectical frameworks (ADFs) have been introduced [Brewka and Woltran, 2010; Brewka et al., 2013]

Hannes Strass

Computer Science Institute Leipzig University, Germany

as a powerful generalization of Dung's framework. ADFs allow for more general interactions between statements, for example support, joint attack, joint support and mixed combinations. Furthermore, ADFs can also handle preferences, on both the statements and the links [Brewka and Woltran, 2010; Brewka et al., 2013] as well as probabilities [Polberg and Doder, 2014]. Moreover, ADFs can not only be seen as an extension of Dung's AFs but also as a target language for compilation from more concrete and application-based languages (e.g. Carneades [Brewka and Gordon, 2010]), and thus, serve as "argumentation middleware" [Brewka et al., 2013].

An ADF consists of a set of statements, a set of links between the statements and for each statement an acceptance condition, a Boolean formula over the parents of the statement. The acceptance of a statement thus only depends on the status of its parents. As for AFs, there are many semantics for ADFs which allow to decide on the status of the statements. One special kind of semantics are the stage [Strass, 2013; Gaggl and Strass, 2014] and the recently introduced nai2 semantics [Gaggl and Strass, 2014]. Both are generalisations of the respective AF semantics (stage and cf2) [Verheij, 1996; Baroni et al., 2005] and based on three-valued conflict-free interpretations. Semantics based on conflict-freeness are also referred to as naive-based semantics in the literature, since they form further refinements of the notion naive, referring to information-maximal conflict-free interpretations. For AFs, naive-based semantics are capable to handle cycles in a more uniform way than admissible-based semantics (see [Gaggl and Dvoˇr´ak, 2014] for an extensive study).

Typical reasoning problems for ADFs are model verification, sceptical and credulous reasoning and existence of a non-trivial interpretation. Analysing the computational complexity of these reasoning problems is a crucial topic for theoretical and practical reasons. First, complexity results often serve as an indicator for how difficult and how expressive a reasoning task can be. Second, knowing about the complexity of a reasoning problem is essential for the development of adequate algorithms and systems. A comprehensive complexity analysis of the ADF semantics defined by Brewka et al. [2013] has been given by Strass and Wallner [2014]. However, the naive-based semantics are a more recent development and their complexity has not received any attention yet.

In this paper, we address these open problems and perform an exhaustive study of the computational complexity of naive-based semantics for abstract dialectical frameworks. More precisely, we analyse all reasoning tasks mentioned earlier (model verification, non-trivial existence, and credulous and sceptical reasoning) for the conflict-free, naive, stage and nai2 semantics. The results show that these tasks are (sometimes considerably) more difficult than their counterparts in AFs. While for the standard Dung semantics (admissible, preferred, complete, stable), their ADF generalisations are mildly more complex (one level up in the polynomial hierarchy [Strass and Wallner, 2014]), for the naive-based semantics, the differences can be far more significant. For example, deciding whether an argument is true in every naive extension can be done in logarithmic space for AFs,while it is hard at least for the second level of the polynomial hierarchy in the case of ADFs. The complexity becomes even higher (completeness for the third level) if we want to check whether a statement is false in every naive interpretation of an ADF. In general, different complexities for entailment of truth and entailment of falsity seems to be quite uncommon in logicbased formalisms. We can trace the reason for this difference in naive-based semantics for ADFs back to the definition of a conflict-free interpretation, which basically requires different strengths of justification depending on which truth value is assigned to a statement: If a statement s is assigned truth value true, then this must be justified by statement s being possibly acceptable, that is, there must be an assignment to the remaining statements such that the acceptance condition of s is fulfilled. On the other hand, if a statement is assigned truth value false, then this must be justified by statement s not being possibly acceptable, that is, a satisfying assignment of the acceptance condition must not exist. Quite possibly even more interesting (and the hardest proof of all our results) is the complexity of deciding existence of non-trivial conflictfree interpretations. We show that the problem is complete for the second level of the Boolean hierarchy [Wechsung, 1985]. The Boolean hierarchy consists of classes that are composed of Boolean combinations of problems from NP and complements thereof. A somewhat better-known example is the class DP, a logical "and" of one NP- and one coNP-problem.

The remainder of the paper is structured as follows. We introduce the necessary background on ADFs and complexity theory in Section 2. The main part of the analysis is performed in Section 3, where we grouped our results according to the four decision problems verification (Section 3.1), existence of a non-trivial interpretation (Section 3.2), and entailment (Section 3.3). We conclude the paper in Section 4.

2 Background

For functions f : A→B and g : C →D, we denote the update of f with g by f ◦ g : A∪C →B ∪D with x ↦→ g(x) if x ∈ C, and x ↦→ f(x) otherwise. So even if x ∈ A∩C and f(x) is defined, we have (f ◦ g)(x) = g(x). For a function f : A → B and b ∈ B we denote f -1 (b) = {a ∈ A | f(a) = b}. For A′ ⊆ A the function f|A′ : A′ →B is the restriction of f's domain to A′ .

We will make use of many standard concepts of classical propositional logic in this paper, including the usual notions of formulas, interpretations and models and satisfiability. Our analysis will be based on three-valued interpretations, mappings v : S → {t, f, u} that assign one of the truth values true (t), false (f ) or unknown (u) to each statement. The three truth values are partially ordered by ≤i according to their information content: we have u <i t and u <i f and no other pair in <i, which intuitively means that the classical truth values contain strictly more information than the truth value unknown. The information ordering ≤i extends in a straightforward way to valuations v1, v2 over S in that v1 ≤i v2 if and only if v1(s) ≤i v2(s) for all s ∈ S.

Given a three-valued interpretation v and a formula ϕ, the partial evaluation of ϕ with v takes the two-valued part of v and replaces the evaluated variables by their truth values.

Definition 1. Let ϕ be a propositional formula over vocabulary S and for an M ⊆ S let v : M → {t, f , u} be a threevalued interpretation. The partial valuation of ϕ by v is the formula ϕv = ϕ[s/t : v(s) = t][s/f : v(s) = f ].

2.1 Abstract dialectical frameworks (ADFs)

An abstract dialectical framework (ADF) is a directed graph whose nodes represent statements or positions which can be accepted or not. The links represent dependencies: the status of a node s only depends on the status of its parents par(s), that is, the nodes with a direct link to s. Each node s has an associated acceptance condition Cs specifying the exact conditions under which s is accepted. Cs is a function assigning to each subset of par(s) one of the truth values t, f . Intuitively, if for some R ⊆ par(s) we have Cs(R) = t, then s will be accepted provided the nodes in R are accepted and those in par(s) \ R are not accepted.

Definition 2. An abstract dialectical framework is a tuple D = (S, L, C) where

• S is a set of statements (positions, nodes),
• L ⊆ S ×S is a set of links,
• C = {Cs}s∈S is a collection of total functions Cs : 2par(s) → {t, f}, one for each statement s. The function Cs is called acceptance condition of s.

It is often convenient to represent acceptance conditions Cs as propositional formulas ϕs over par(s). (We will do so in this paper, and furthermore restrict ourselves to finite ADFs.) Then, clearly, for M ⊆ par(s) we have Cs(M) = t iff M |= ϕs. It might be the case that a link (r, s) ∈ L in an ADF bears no actual significance. Formally, r is redundant in ϕs iff for every two-valued interpretation v : par(s) → {t, f}, the formulas ϕv◦{r↦→t} s and ϕv◦{r↦→f} s are equivalent. That is, if (r, s) is redundant then v(r) has no influence on the truth value of ϕvs whatsoever. Several semantics for ADFs can be defined by using three-valued interpretations v to partially evaluate acceptance formulas ϕs [Brewka et al., 2013; Gaggl and Strass, 2014]. We use the following three:

Definition 3. Let D = (S, L, C) be an ADF. A three-valued interpretation v : S → {t, f , u} is

• conflict-free, i.e. v ∈ cfi(D), iff for all s ∈ S we have:
• v(s) = t implies that ϕvs is satisfiable,
• v(s) = f implies that ϕvs is unsatisfiable;

• naive, i.e. v ∈ nai(D), iff v is ≤i-maximal conflict-free;
• stage, i.e. v ∈ stg(D), iff the set vu = v-1 (u) is ⊆-minimal with respect to v being conflict-free.

The following definitions are from [Gaggl and Strass, 2014]. Definition 4. Let D = (S,L,C) be an ADF and p, s ∈ S. We say that s depends on p if there is a path from p to s in L but no path from s to p in L. Now let M ⊆ S. A statement s ∈ S is independent modulo M iff for each p ∈ S, if s depends on p then p ∈ M. A set M ⊆ S is independent iff there is no s ∈M that depends on a p ∈ S \M. Lastly, define indD(M) = {s ∈ S | s is independent modulo M in D}.

Note that dependence here implicitly speaks about strongly connected components (SCCs). Given an independent subset M of statements of an ADF, ignoring all other statements again yields an ADF.

Definition 5. Let D = (S, L, C) be an ADF and M ⊆ S be an independent set. The ADF D restricted to M is given by D|M = (M, L ∩ (M × M), {ϕs}s∈M ).

Note that D|M really is an ADF since its acceptance formulas by presumption do not mention statements not in M.

Definition 6. Let D = (S,L,C) be an ADF, M ⊆ S and v : M → {t, f, u}. The ADF D reduced with v on M is given by JDKvM = (S, JLKvM , {JϕsKvM }s∈S ) with

That is, clean(ϕvs ) removes redundant parents of s fromϕvs .

Definition 7. Let D = (S, L, C) be an ADF. The set of nai 2 interpretations of D is recursively defined as follows:

2.2 Complexity theory

Assume some fixed finite vocabulary Σ with |Σ| > 1. A language L ⊆ Σ∗ is in P iff it can be recognised by a deterministic Turing machine in polynomial time. Complexity class NP contains all problems L that have a polytimecomputable witness relation; that is, L ∈ NP iff there are WL ∈ P and k ∈ N such that: x ∈ L iff there is a y such that (x, y) ∈WL and |y| ≤ |x|k . For any class C of languages, its complement class is coC = {L ∣∣ L ∈ C}. For example, the class coNP contains all languages L whose complement L = Σ∗ \ L is in NP. These two classes give rise to the polynomial hierarchy, that can be defined (using oracle Turing machines) as follows: ∆P0 = ΣP0 = ΠP0 = P, and for i ≥ 0, ∆Pi+1 = PΣPi , ΣPi+1 = NPΣPi , ΠPi+1 = coNPΣPi . For any complexity class C, a Turing machine with access to a

C-oracle can be understood as having a constant-time decision subroutine for problems in C. For each level i of the polynomial hierarchy, the classes ΣPi and ΠPi have canonical complete problems. For ΣPi it is as follows: Given a quantified Boolean formula (QBF) Φ = ∃P1∀P2∃P3 . . .QiPiψ, determine whether Φ is true, where Qi ∈ {∀, ∃} depending on whether i is even or odd. For ΠPi the canonical complete problem is similar, but starts with universal quantification.

While these classes are fairly standard, NP and coNP also give rise to the so-called Boolean hierarchy. It is rather little-known and defined as follows [Wechsung, 1985]. Firstly, for given complexity classes C1 and C2 define the new classes C1 C2 = {L1 ∩L2 | L1 ∈ C1,L2 ∈ C2} and C1 C2 = {L1 ∪L2 | L1 ∈ C1,L2 ∈ C2}. Next, set C BH 0 = D BH 0 = P and for i ≥ 0 define C BH i+1 = coNP D BH i and D BH i+1 = NP C BH i . 1 (Intuitively, C BH i is for "conjunction" and D BH i is for "disjunction".) For example, D BH 1 = NP and C BH 1 = coNP, while D BH 2 = NP C BH 1 = NP coNP and C BH 2 = coNP D BH 1 = coNP NP. The class C BH 2 was independently discovered and called DP by Papadimitriou and Yannakakis [1982]. Its complement coDP = D BH 2 contains all languages L for which there are L1 ∈ NP and L2 ∈ coNP with L = L1 ∪ L2. The Boolean hierarchy and the polynomial hierarchy are closely interrelated: Chang and Kadin [1996] showed that the polynomial hierarchy collapses (to the third level) if the Boolean hierarchy collapses.

3 Complexity Results

We will consider the following decision problems for any semantics σ ∈ {cfi , nai , stg , nai 2}.

• Verσ: Given an ADF D over S and an interpretation v : S → {t, f , u}, is v ∈ σ(D)?
• Existsσ: Given an ADF D over S, does there exist a non-trivial interpretation v ∈ σ(D), that is, one with v(S) ̸= {u}?
• Credtσ / Credfσ : Given an ADF D over S and an s ∈ S, does there exist an interpretation v ∈ σ(D) with v(s) = t / v(s) = f ?
• Sceptσ / Scepfσ : Given an ADF D over S and an s ∈ S, is v(s) = t / v(s) = f for all v ∈ σ(D)?

In several reductions of this paper, we consider quantified Boolean formulas over vocabularies P ⊎Q with their matrix ψ in either DNF (a disjunction of monomials) or CNF (a conjunction of clauses). They will be used to provide hardness results through reducing checking whether the QBF evaluates to true to some relevant problem at hand. Sometimes, we cannot use ψ as is, but have to replace atoms from part of its vocabulary, say P, by new literals from a distinct copy of P, the atoms P ′ = {p′ | p ∈ P}. We will then denote by ψ′ the formula obtained from ψ by replacing all positive occurrences of an atom p ∈ P by the literal ¬p′ for the respective p′ ∈ P ′ . For example, for the DNF ψ = (p1 ∧ q1 ∧¬p2) ∨ (¬q2 ∧¬p1 ∧ p3) we get ψ′ = (¬p′1 ∧ q1 ∧¬p2) ∨ (¬q2 ∧¬p1 ∧¬p′3 ). The following property of this replacement will be important for us.

1 This is the Boolean hierarchy between ∆P1 = P and ∆P2 ; there is a Boolean hierarchy between ∆Pi and ∆Pi+1 for all i ≥ 1 [Chang and Kadin, 1996] (using ΣPi and ΠPi instead of NP and coNP).

Proposition 1. Let ψ be a DNF over P . For every interpretation v : P → {t, f}, there exists a w : P ∪ P ′ → {f , u} such that ψv is a tautology if and only if ψ′w is a tautology.

A similar result holds for satisfiability if ψ is in CNF. We are now ready to present the main results of this paper, tight complexity bounds for all semantics among conflictfree, naive, stage and nai2 for all decision problems introduced above. The results are grouped together in subsections according to the decision problems.

3.1 Interpretation verification

We start out with verifying if a given interpretation is conflictfree. Roughly, this is done using one satisfiability check and one unsatisfiability check, and the completeness result tells us that we most likely cannot do any better.

Proposition 2. Vercfi is DP-complete.

Proof. in DP: Let D be an ADF over S and v : S → {t, f, u} be an interpretation. To verify that v is conflict-free for D, we have to verify that (1) for all s ∈ S with v(s) = t, the formula ϕvs is satisfiable, and (2) for all s ∈ S with v(s) = f , the formula ϕvs is unsatisfiable. This can be done in DP by verifying that ∧s∈S,v(s)=t ϕvs is satisfiable and ∨s∈S,v(s)=f ϕvs is unsatisfiable. Clearly these formulas can be computed in polynomial time.

DP-hard: Let φ and ψ be propositional formulas over disjoint vocabularies P1 and P2, respectively. We construct an ADF over statements S = P1 ∪ P2 ∪ {x, y} and an interpretation v : S → {t, f, u} such that v is conflictfree for D if and only if φ is satisfiable and ψ is unsatisfiable. Set ϕp = ¬p for all p ∈ P1 ∪ P2, furthermore set ϕx = φ and ϕy = ψ. Finally, define v such that p ↦→ u for p ∈ P1 ∪ P2, and x ↦→ t and y ↦→ f . ✷

To showcase the reductions used in the proofs of our results, we present one particular reduction that is used to show the ΠP2 -hardness of most interpretation verification problems.

Reduction 1. Let Φ = ∃P∀Qψ be a QBF with ψ in DNF. Define an ADF DΦ over S = P ∪ P ′ ∪ Q ∪ {y, z} with:

Here ψ′ is ψ where all positive occurrences of p are replaced by ¬p′ . Finally, define the interpretation v : S → {t, f, u} such that v(y) = t and all other statements are mapped to u.

Intuitively, p and p′ serve to guess a valuation for P where setting p ∈ S to false encodes setting p ∈ P to false, and setting p′ ∈ S to false encodes setting p ∈ P to true. All p, p′ ∈ S cannot be set to true, and only be set to false if z is false and y is true; in turn, z can only be set to false if ¬ψ′ is unsatisfiable; statement y can only be set to t or u. Setting y to true in a conflict-free interpretation v guarantees that for each p ∈ P at most one of p is false or p′ is false in v, but never both. These ideas are reused and (sometimes significantly) elaborated upon in later results.

Recall that an interpretation v : S → {t, f, u} is naive iff it is conflict-free and ≤i-maximal with respect to being conflict-free. Thus, to verify that a given interpretation v is not naive, we first check (using an NP oracle) whether v is conflict-free. If v is not conflict-free, we are done; otherwise, we can guess an interpretation v′ with v <i v′ and verify in DP (using the NP-oracle again) that v′ is conflict-free. Once more, this is the best we can do.

For verifying stage interpretations, membership works in the same way as for naive. For hardness, a close look at Reduction 1 reveals that it also works for stage semantics.

The same hardness reduction (Reduction 1) even works for the nai2 semantics. It is somewhat harder to show containment in ΠP2 via a reduction to Vernai : intuitively, this is done by parallelising the single (independent) verifications of nai interpretations in all SCCs of a given ADF D.

Proof. in ΠP2 : We show a reduction to Vernai . Let D be an ADF over S and the interpretation v : S → {t, f , u} be given. We recursively compute the unique decomposition of D with respect to v. In the following we denote the independent sets for each recursive call by Mi for 0 ≤ i < n, that is, M0 = indD(∅) and Mi+1 = ind JDKviMi (Mi) with vi = v|Mi . In each recursive call we make a new, distinct copy Di of the ADF D|Mi and the respective restricted interpretation vi = v|Mi , that is, for 0 ≤ i < n define an ADF Di = (Si,Li,Ci) with statements Si = {si | s ∈Mi}, links Li = {(si, ti) | si, ti ∈ Si, (s, t) ∈ L}, acceptance formulas ϕsi = ϕs[s/si : s ∈Mi] and furthermore an interpretation wi : Si → {t, f , u} with wi(si) = vi(s) for all s ∈Mi. Let Mk = S be the independent set for the last recursive call. (Clearly k < n.) Now we have that v ∈ nai2(D) if and only if w′ ∈ nai(D′ ), where

The computation of D′ can be done in at most n steps (for |S| = n) with at most n(n+1) 2 statements in D′ . ✷

3.2 Existence of non-trivial interpretations

Deciding whether a given ADF D has at least one non-trivial conflict-free interpretation turns out to be complete for the less well-known complexity class coDP. Intuitively, a coDPproblem allows us to choose whether we "want" to solve an NP- or a coNP-problem, but we have to solve at least one of them correctly. Showing coDP-hardness for Existscfi is comparably easy. The canonical coDP-complete problem is the following, SAT-OR-UNSAT: Given two propositional formulas φ and ψ, is φ satisfiable or ψ unsatisfiable? Note that the "or" is to be understood logically, that is, it suffices to answer at least one of the questions correctly. The reduction from SAT-OR-UNSAT to Existscfi now works as follows: given two propositional formulas φ and ψ over vocabularies P1 and P2, we construct an ADF D over S = P1 ∪ P2 ∪ {y, z} with ϕp = ¬p for p ∈ P1 ∪ P2, ϕy = ¬y ∨ φ, and ϕz = ¬z ∧ ψ. It is easy to see that D has a non-trivial conflict-free interpretation v with v(y) = t iff φ is satisfiable, and that D has a non-trivial conflict-free interpretation v with v(z) = f iff ψ is unsatisfiable. In combination, D has a non-trivial conflictfree interpretation iff φ is satisfiable or ψ is unsatisfiable.

Showing membership of Existscfi for coDP is quite tricky. The first useful observation is that there are essentially only two distinct types of non-trivial conflict-free interpretations:

1. those v : S → {t, f, u} with v-1 (t) ̸= ∅, that is, where some statement is mapped to true;
2. those with v(S) ⊆ {u, f} and v-1 (f) ̸= ∅, that is, all statements are mapped to undefined or false and at least one is mapped to false.

The proof works by showing that existence of non-trivial conflict-free interpretations of type (1) can be decided in NP, and that the existence of those of type (2) can be decided in coNP. In combination, membership for coDP follows.

Showing the first part is straightforward: to decide whether some statement s ∈ S can be set to true without violating conflict-freeness, we construct the propositional formula ∨s∈S ϕ{s↦→t} s and check if it is satisfiable. If for some s ∈ S the formula ϕ{s↦→t} s is satisfiable, then v : S → {t, f , u} with v(s) = t and v(s′ ) = u for s′ ∈ S \ {s} is conflict-free. Otherwise, no s ∈ S can be set to true in a conflict-free way.

Showing the second part about interpretations v : S → {t, f, u} with v(S) ⊆ {u, f} (we call them uf-interpretations) constitutes the main portion of the proof. Roughly, conflict-free uf-interpretations are closed under the greatest lower bound operator ⊔i associated to the information ordering ≤i on interpretations. That is, whenever v1 and v2 are uf-interpretations that are conflict-free for D, then the interpretation v1 ⊔i v2 is a uf-interpretation that is conflict-free for D as well. Since both v1 ≤i v1 ⊔i v2 and v2 ≤i v1 ⊔i v2 by definition, there is a unique ≤i-greatest conflict-free uf-interpretation vmax : S → {t, f, u} of D. Our task is to decide whether vmax is non-trivial. We first show how to do this by computing vmax in polynomial time using an NP oracle. The procedure works constructively and begins with the interpretation v0 : S → {f}, that is, mapping all statements to false. The computation now stepwise (j = 0, 1, . . . , n-1) reassigns vj+1(s) = u for s ∈ v-1 j (f) whenever it is the case that assigning vj(s) = f is actually not justified because ϕvj s is satisfiable (otherwise, it keeps vj+1(s) = vj(s) = f). To answer the satisfiability queries, the procedure can use the NP-oracle. The proof finally shows how to combine all the oracle queries into one satisfiability check. This is done by encoding the whole computation into a propositional formula φcfi of polynomial size such that the formula is satisfiable if and only if there is a possible computation that starts with v0(S) = {f} and ends in the trivial vn(S) = {u}. Since such a computation would show that vmax is trivial, there is a non-trivial conflict-free uf -interpretation of D if and only if the formula φcfi is unsatisfiable. This then shows containment in coNP for checking whether there is a non-trivial conflict-free interpretation of type (2), and thus concludes the coDP-containment proof.

Fortunately, this amount of work "pays off" in that deciding the existence of non-trivial conflict-free interpretations also decides the existence of naive, stage and nai2 interpretations. The first technical result towards establishing that is the following lemma. It shows how every conflict-free interpretation v gives rise to a naive (or stage) interpretation v′ that is "above v" with respect to some ordering. In case of naive, the ordering is clearly the information ordering ≤i. In case of stage, the ordering is given by comparing the statements that are assigned the truth value u by the two interpretations.

Lemma 7. Let D be an ADF over S. For every interpretation v : S → {t, f , u} that is conflict-free for D, there exists:

1. a naive interpretation v′ : S → {t, f, u} with v ≤i v′ ;
2. a stage interpretation v′′ : S → {t, f, u} with v′′u ⊆ vu.

The lemma can be used to show that not only do the nontrivial existence problems coincide, but also credulous entailment for conflict-free and naive semantics are equivalent. Intuitively, if an ADF D has a conflict-free interpretation v with, say, v(s) = t, then the lemma above guarantees the existence of a naive w with v ≤i w and thus w(s) = v(s) = t.

Proposition 8. The following decision problems coincide:

1. Existscfi, Existsnai , Existsstg, Existsnai2 ;
2. Credtcfi and Credtnai ;
3. Credfcfi and Credfnai .

3.3 Entailment

While verification is a quite basic reasoning task, and nontrivial interpretation existence is mostly used to figure out if a given knowledge base is sensible at all, the entailment problem is most likely to be repeatedly used in practice. Recalling that ADFs are intended for modelling argumentation scenarios, entailment queries then allow to answer questions about these scenarios, such as, "Is it the case that there is one possible interpretation of this scenario where statement a is true?" For the conflict-free semantics, this problem is, while infeasible in a conservative sense, still relatively easy.

Astonishingly, for similar questions of the form, "Is it the case that there is one possible (conflict-free) interpretation of this scenario where statement a is false?", giving an answer becomes harder! This asymmetry is quite remarkable, and has its cause in the asymmetry of the definition of a conflict-free interpretation: v : S → {t, f , u} is conflict-free iff for each s ∈ S with v(s) = t the formula ϕvs is satisfiable, and for each s ∈ S with v(s) = f the formula ϕvs is unsatisfiable. So in one case, there is a satisfiability check, in the other there is an unsatisfiability check. To decide credulous entailment, we clearly have to guess an interpretation v : S → {t, f , u} with a desired property (such as v(s) = t or v(s) = f ). And while the witnesses for verifying v(s) = t can be guessed alongside v, such is not possible when having to verify v(s) = f . Formally, the hardness part of the result below is proved via a reduction from the problem of deciding whether a quantified Boolean formula ∃P∀Qψ is true.

There is a straightforward way to show that a statement s ∈ S is not sceptically entailed as true by an ADF D over S: guess an interpretation v : S → {t, f , u} with v(s) ̸= t and show that v is naive. Since Vernai is in ΠP2 , this straightforward approach yields containment of Sceptnai in ΠP3 . Fortunately, there is an easier way: we guess an interpretation v : S → {t, f , u} with v(s) = u, and verify (using the NP oracle) that v is conflict-free for D, while the augmented interpretation v ◦ {s ↦→ t} is not conflict-free for D. Intuitively, this identifies statement s ∈ S as a "troublemaker", as the one reason that violates conflict-freeness in all interpretations with at least as much information as v. Since among these interpretations at least one must be naive, we have our desired counterexample for sceptical entailment. This yields containment in ΠP2 ; as it turns out, that is the best possible bound.

The straightforward approach to decide sceptical entailment of truth clearly also works for sceptical entailment of falsity. In this case, however, it turns out that there is no shortcut. For the (quite technical) proof of the result, we adapt and combine proof techniques from [Strass and Wallner, 2014, Theorem 20] and Theorem 3.

For naive semantics, we have seen (1) an asymmetry in deciding (credulous/sceptical) truth and falsity; and (2) a steady rise in complexity from credulous truth up to sceptical falsity. For stage semantics, surprisingly, these differences vanish: All four decision problems are (more or less) equally hard, namely in the third level of the polynomial hierarchy. For the first problem, this is shown by considering QBFs ∃P∀Q∃Rψ.

For hardness of deciding credulous falsity, we can use a simple extension of the hardness construction used above: basically, the construction relies on a statement y that can be set to u if the given QBF ∃P∀Q∃Rψ is true, and must be set to f otherwise (due to the inherent ⊆-minimisation of vu in stage semantics). The actual reduction now works over a statement z with acceptance formula ϕz = y; consequently, z can be set to true iff y can be set to u. In the extended construction below, we now add another statement a with acceptance formula ϕa = ¬z. Both statements will always be assigned opposite truth values from {t, f}, thus proving the next result.

Proposition 14. Credfstg is ΣP3 -complete.

To show that a statement s is not sceptically entailed as false in an ADF D, we guess an interpretation v : S → {t, f, u} with v(s) ̸= f and verify in ΠP2 that v is stage. This approach is optimal, as completeness shows.

In the step from Scepfstg to Sceptstg we can use the same construction extension as in the step from Credtstg to Credfstg .

For the nai2 semantics, we can directly use that the relevant entailment decision problems (or their complements, respectively) are polynomially interreducible.

Proposition 17. The following problems can be polynomially reduced to each other:

• Credtnai2 and Credfnai2 ,
• Sceptnai2 and Scepfnai2 ,
• co-Scepfnai2 and Credtnai2 .

Together with the observation that the hardness reduction of Theorem 12 works for the nai 2 semantics as well, the proposition leads to the following results.

Theorem 18. Credtnai2 and Credfnai2 are ΣP3 -complete. Sceptnai2 and Scepfnai2 are ΠP3 -complete.

4 Discussion

We presented numerous novel results on the computational complexity of naive-based semantics for abstract dialectical frameworks. An overview is above in Table 1. The main lesson learned is that naive-based semantics for ADFs are - computationally speaking - not at all "naive".

Our analysis paves the way for implementing naive-based ADF semantics, for example by adding adequate ASP encodings for the verification and existence problem to the DIAMOND system [Ellmauthaler and Strass, 2014]. For the sceptical and credulous entailment problems in the third level of the polynomial hierarchy, encodings based on QBFs seem possible [Diller et al., 2014]. In future work, we also intend to identify computationally more amenable fragments; the subclass of bipolar ADFs is a promising candidate. Furthermore, the recently introduced stg2 semantics [Gaggl and Strass, 2014] is as yet unanalysed in terms of complexity.