d4-journals-jair-2022-0068 (d4-journals-jair-2022-0068)

Given a support of \(\tau\) types \((F_t,a_t)\) with binary-rational masses \(\mu_t>0\) summing to \(1\), and a binary-rational threshold \(\theta\in[0,1]\), let \(z_t=1\) exactly when \(a_t\) belongs to some weakly preferred extension of \(F_t\), and \(z_t=0\) otherwise. Decide whether \(\sum_{t=1}^{\tau}\mu_t z_t\ge\theta\).

A society is given by its support: the list of the \(\tau\) distinct types \((F_t,a_t)\) with positive binary-rational masses \(\mu_t\) summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
Each \(F_t=(A_t,R_t)\) is an explicitly given finite directed argumentation framework, with \(R_t\subseteq A_t\times A_t\) and \(a_t\in A_t\); self-attacks are allowed. Set \(m=\max_t|A_t|\), and let \(L\) be the total binary input length. State running times in \(m,\tau,L\).
For \(F=(A,R)\) and \(E\subseteq A\), define \(E^+=\{b\in A:\exists e\in E,\ (e,b)\in R\}\) and let \(F^E\) be the induced framework on \(A\setminus(E\cup E^+)\).
Define the family \(\mathcal W(F)\) recursively: \(\varnothing\in\mathcal W(F)\); a nonempty \(E\subseteq A\) belongs to \(\mathcal W(F)\) exactly when it is conflict-free and every \(y\in A\) attacking an element of \(E\) satisfies \(y\notin\bigcup_{D\in\mathcal W(F^E)}D\). Conflict-free means \(R\cap(E\times E)=\varnothing\).
A weakly preferred extension is an inclusion-maximal member of \(\mathcal W(F)\). Define \(z_t\in\{0,1\}\) to equal \(1\) exactly when some weakly preferred extension of \(F_t\) contains \(a_t\).
Given a binary-rational threshold \(\theta\in[0,1]\), is deciding whether \(\sum_{t=1}^{\tau}\mu_tz_t\ge\theta\) solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For a single finite argumentation framework, deciding whether a designated argument belongs to some weakly preferred extension is PSPACE-complete.

Result

The decision problem is \(\mathsf{PSPACE}\)-complete, and therefore \(\mathsf{NP}\)-hard, under polynomial-time many-one reductions.

Consequently, it is polynomial-time solvable in \(m,\tau,L\) if and only if \(\mathsf{P}=\mathsf{PSPACE}\). The hardness already holds for \(\tau=1\). Below, the upper bound handles arbitrary support and exact rational arithmetic.

1. Credulous acceptance does not require testing maximality

For a finite framework \(G\), define
\[ C(G)=\bigcup_{E\in\mathcal W(G)}E. \]

Lemma. An argument \(a\) belongs to some weakly preferred extension of \(G\) if and only if \(a\in C(G)\).

Proof. Every weakly preferred extension belongs to \(\mathcal W(G)\), proving one implication.

Conversely, suppose \(a\in E\in\mathcal W(G)\). Among the members of \(\mathcal W(G)\) containing \(E\), choose one, \(P\), of maximum cardinality. This choice exists because the argument set is finite. If some \(D\in\mathcal W(G)\) strictly contained \(P\) as a subset, meaning \(P\subsetneq D\), then \(D\) would also contain \(E\) and have larger cardinality. Thus no such \(D\) exists, so \(P\) is weakly preferred and contains \(a\). \(\square\)

In particular,
\[ z_t=1\quad\Longleftrightarrow\quad a_t\in C(F_t). \]

2. An explicit polynomial-space algorithm

Fix \(F=(A,R)\). For \(S\subseteq A\), let \(F[S]\) denote the induced framework on \(S\), and write
\[ C(S)=C(F[S]). \]

For a nonempty \(E\subseteq S\), define its attackers and its reduct vertex set by
\[ B_S(E)=\{y\in S:\exists e\in E,\ (y,e)\in R\}, \]
\[ Q_S(E)=S\setminus\bigl(E\cup E_S^+\bigr), \qquad E_S^+=\{b\in S:\exists e\in E,\ (e,b)\in R\}. \]

The defining recursion gives exactly
\[ C(S)= \bigcup_{\substack{\varnothing\ne E\subseteq S\\ R\cap(E\times E)=\varnothing\\ B_S(E)\cap C(Q_S(E))=\varnothing}} E, \qquad C(\varnothing)=\varnothing. \]

Indeed, the last condition says precisely that every attacker of \(E\) is absent from every member of \(\mathcal W(F[S]^E)\). Here
\[ F[S]^E=F[Q_S(E)]. \]
The empty extension contributes nothing to the union.

This identity gives a recursive algorithm: enumerate all nonempty subsets \(E\subseteq S\), check conflict-freeness, recursively compute \(C(Q_S(E))\), and add \(E\) to the accumulated union when the attacker condition holds. Self-attacks are handled by the conflict-freeness check.

Termination and correctness. Since \(E\ne\varnothing\),
\[ |Q_S(E)|\le |S|-1. \]
Every recursive call therefore has fewer arguments. Correctness follows by induction on \(|S|\), using the displayed identity.

Space bound. Represent subsets by \(m\)-bit vectors. Each recursion frame stores only a constant number of such vectors and enumeration counters. The recursion depth is at most \(m+1\), so the framework computation uses \(O(m^2)\) working bits, including an adjacency matrix.

Time bound. After indexing the vertices, the nonrecursive work per candidate subset can conservatively be bounded by \(O(m^3)\) bit operations. A call on \(n\) vertices considers fewer than \(2^n\) candidates, and every recursive call has at most \(n-1\) vertices.

Let
\[ H_0=1,\qquad H_n=2^n(H_{n-1}+1). \]
The recursive running time is bounded by \(O(m^3H_n)\). Moreover,
\[ \frac{H_n}{2^{n(n+1)/2}} = 1+\sum_{j=0}^{n-1}2^{-j(j+1)/2} \le 1+\sum_{j=0}^{\infty}2^{-j} =3. \]
Thus all \(\tau\) acceptance indicators can be computed sequentially in
\[ O\!\left(\tau m^3\,2^{m(m+1)/2}\right) \]
time, reusing \(O(m^2)\) working space.

3. Exact comparison of the weighted sum

Write the input rationals as
\[ \mu_t=\frac{p_t}{q_t}, \qquad \theta=\frac{p_0}{q_0}, \]
with positive integer denominators. Define
\[ D=\prod_{t=0}^{\tau}q_t. \]
Then
\[ \sum_{t=1}^{\tau}\mu_tz_t\ge\theta \quad\Longleftrightarrow\quad \sum_{t=1}^{\tau}p_tz_t\frac{D}{q_t} \ge p_0\frac{D}{q_0}. \]

The bit length of \(D\) is \(O(L)\), because it is bounded by the sum of the input denominator lengths, up to an additive constant. Each summand has \(O(L)\) bits. Since the masses sum to \(1\), the accumulated numerator is at most \(D\).

Compute \(D\) first, then process the frameworks sequentially and accumulate the corresponding integer summands. Schoolbook multiplication and division give a conservative \(O(L^3)\) bound for all rational arithmetic, using \(O(L)\) working bits.

Combining this with the recursive algorithm yields
\[ \text{time } O\!\left(\tau m^3\,2^{m(m+1)/2}+L^3\right), \qquad \text{space }O(m^2+L). \]
Because the frameworks are explicit, \(m\) is bounded by the input length. The space bound is therefore polynomial in \(L\), proving membership in \(\mathsf{PSPACE}\).

4. Hardness

Use the stated premise that, for a single finite framework, credulous acceptance under weakly preferred semantics is \(\mathsf{PSPACE}\)-complete.

Given an instance \((F,a)\) of that problem, construct the society
\[ \tau=1,\qquad (F_1,a_1)=(F,a),\qquad \mu_1=1, \qquad \theta=1. \]

This is a valid society: its single mass is positive and sums to \(1\), and its support consists of one distinct type. The construction takes polynomial time.

Its weighted decision condition is
\[ \mu_1z_1\ge\theta \quad\Longleftrightarrow\quad z_1\ge1 \quad\Longleftrightarrow\quad z_1=1. \]
Thus it holds exactly when some weakly preferred extension of \(F\) contains \(a\). This proves \(\mathsf{PSPACE}\)-hardness and hence \(\mathsf{NP}\)-hardness.

Together with the upper bound, this settles the requested classification.

⟨structured verdict parsed — rendered above⟩

The claimed classification is correct: the problem is \(\mathsf{PSPACE}\)-complete and hence \(\mathsf{NP}\)-hard. The proof has one minor wording error, but no substantive mathematical gap.

Step-by-step verification

• Removing the maximality requirement

The lemma is valid. Every weakly preferred extension is a member of \(\mathcal W(G)\), giving the forward implication.

For the converse, the family of members of \(\mathcal W(G)\) containing a fixed \(E\) is nonempty and finite. A maximum-cardinality member \(P\) cannot have a strict superset in \(\mathcal W(G)\): that superset would also contain \(E\) and contradict the choice of \(P\). Thus \(P\) is inclusion-maximal and retains the designated argument.

Minor issue: The sentence beginning “If some \(D\)” reverses the containment relation in words. “\(D\) … strictly contained \(P\)” contradicts the immediately supplied formula \(P\subsetneq D\). The formula and subsequent reasoning make the intended direction unambiguous.

Minimum clarification: Replace that phrase with “If some \(D\in\mathcal W(G)\) strictly contained \(P\) as a proper subset, that is, \(P\subsetneq D\).” More simply, write “If \(P\) had a strict superset \(D\in\mathcal W(G)\).”

• Identity for the union of weakly admissible sets

The displayed recursion for \(C(S)\) follows directly from the supplied definition. It includes exactly the nonempty conflict-free sets whose attackers are absent from the union of the reduct’s weakly admissible sets.

The identity \(F[S]^E=F[Q_S(E)]\) uses the correct induced reduct. Attackers outside the reduct automatically fail to belong to its union, as required. The empty extension contributes no arguments. Self-attacks are correctly excluded by the conflict-freeness test.

• Termination and correctness

Every recursive candidate is nonempty, so removing \(E\) reduces the vertex count by at least one. Consequently, recursion terminates and induction on \(|S|\) applies. The base case \(C(\varnothing)=\varnothing\) is correct.

Enumerating every candidate and accumulating precisely those satisfying the recursive condition computes the stated union. No monotonicity or closure property of \(\mathcal W\) is assumed.

• Framework computation: space and time

The space accounting is sound. Each frame needs a constant number of subset vectors and counters of \(O(m)\) bits. With at most \(m+1\) frames and an \(O(m^2)\)-bit adjacency matrix, the framework computation uses \(O(m^2)\) working bits.

The recurrence \(H_n=2^n(H_{n-1}+1)\) conservatively bounds the branching and local work. The normalized recurrence and its displayed summation are correct, including the initial value. The comparison \(j(j+1)/2\ge j\) holds for every integer \(j\ge0\), validating the bound by \(3\).

Thus the claimed time bound \(O(\tau m^3 2^{m(m+1)/2})\) is valid. Sequential processing permits reuse of the framework workspace.

• Exact rational comparison

All denominators are positive, so multiplying the threshold comparison by \(D\) preserves its direction. Every \(D/q_t\) is an integer.

The product \(D\) has \(O(L)\) bits. Input numerators also have \(O(L)\) bits, so the displayed integer summands have \(O(L)\) bits. Positivity and normalization of the masses ensure that every partial accumulated numerator is at most \(D\).

Schoolbook arithmetic on these integers, across at most \(O(L)\) input rationals, fits the conservative \(O(L^3)\) time and \(O(L)\) workspace bounds. Thresholds \(0\) and \(1\) cause no exception.

• Membership in \(\mathsf{PSPACE}\)

The combined space bound \(O(m^2+L)\) is polynomial in the explicit input length. The algorithm therefore establishes membership in \(\mathsf{PSPACE}\), despite its exponential running time.

• Hardness and final classification

The single-framework \(\mathsf{PSPACE}\)-completeness result is expressly supplied by the task, so its use requires no additional external theorem.

The reduction preserves the framework and designated argument, uses one valid support type with mass \(1\), and sets threshold \(1\). Its decision condition is exactly \(z_1=1\). The construction is polynomial and establishes \(\mathsf{PSPACE}\)-hardness, already for \(\tau=1\).

Together with membership, this proves the claimed completeness. The stated equivalence between polynomial-time solvability and \(\mathsf{P}=\mathsf{PSPACE}\) also follows.

⟨structured verdict parsed — rendered above⟩