d4-conf-aaai-2023-1322 (d4-conf-aaai-2023-1322)

Given a finite type set \(T\), positive rational masses \(\mu_t\) summing to \(1\), a well-formed type-level CAF with claim map \(q:T\to Q\), an asymmetric transitive preference relation, a target claim set \(C\subseteq Q\), and \(\sigma\in\{\mathrm{prf},\mathrm{sem},\mathrm{stg}\}\), form the population as intervals \(I_t\) of lengths \(\mu_t\), with attacks and preferences lifted by type. Modulo null sets, let an accepted measurable set \(E\) induce support \(S(E)=\{t:\lambda(E\cap I_t)>0\}\), and interpret \(S(E)\) using the paper's type-level Reduction 1 semantics. Decide whether there exists such an \(E\) with \(S(E)\in\sigma^1_p(F)\) and \(q(S(E))=C\).

A society is given by its support: a finite list \(T\) of \(\tau\) types with positive binary rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
The input also specifies a finite claim set \(Q\), a map \(q:T\to Q\), an attack relation \(R\subseteq T\times T\), an asymmetric transitive relation \(\succ\subseteq T\times T\), a target \(C\subseteq Q\), and \(\sigma\in\{\mathrm{prf},\mathrm{sem},\mathrm{stg}\}\). Equal claims must have identical outgoing attacks: \(q(t)=q(u)\Rightarrow\{v:(t,v)\in R\}=\{v:(u,v)\in R\}\). Self-attacks are allowed; \(t\succ u\) means that \(t\) is stronger than \(u\).
Define \(R_1=\{(t,u)\in R:\neg(u\succ t)\}\) and \(G=(T,R_1)\). Use standard preferred, semi-stable, or stage argumentation semantics on \(G\), respectively.
Partition \([0,1)\) into intervals \(I_t\) of lengths \(\mu_t\); attacks and preferences between points are those of their types. For a measurable accepted set \(E\), considered modulo Lebesgue null sets, define \(S(E)=\{t:\lambda(E\cap I_t)>0\}\). Acceptance means \(S(E)\in\sigma(G)\), and its claims are \(q(S(E))=\{q(t):t\in S(E)\}\).
Is deciding whether there exists such an \(E\) with \(q(S(E))=C\) in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard, for each fixed \(\sigma\)? State running times in \(m=|Q|\), \(\tau\), and the total input bit length \(L\).
For finite argument populations, this exact claim-set verification problem is \(\Sigma_2^{\mathrm{P}}\)-complete for all three semantics, even with transitive preferences. [Source](https://arxiv.org/html/2204.13305v1).

Result

For each fixed \(\sigma\in\{\mathrm{prf},\mathrm{sem},\mathrm{stg}\}\), the decision problem is \(\Sigma_2^{\mathrm P}\)-complete, and hence \(\mathrm{NP}\)-hard. Thus a polynomial-time algorithm would imply \(\mathrm P=\mathrm{NP}\).

A deterministic algorithm takes \(2^\tau\operatorname{poly}(L)\) time. The relevant exponential parameter is the support size \(\tau\); the masses do not affect the answer.

1. Exact reduction to a finite problem

For every \(S\subseteq T\), define the measurable set
\[ E_S=\bigcup_{t\in S}I_t. \]
Because every mass is positive,
\[ \lambda(E_S\cap I_t)= \begin{cases} \mu_t>0,&t\in S,\\ 0,&t\notin S. \end{cases} \]
Consequently, \(S(E_S)=S\).

Conversely, every measurable \(E\) determines a subset \(S(E)\subseteq T\). Changing \(E\) on a null set preserves all the quantities \(\lambda(E\cap I_t)\), so this subset is well-defined modulo null sets.

By the definition of acceptance in the question, we therefore have the exact equivalence
\[ \exists E\text{ accepted with }q(S(E))=C \quad\Longleftrightarrow\quad \exists S\subseteq T:\ S\in\sigma(G)\text{ and }q(S)=C. \]
In particular, neither the numerical values of the positive masses nor the placement of the intervals changes the answer.

2. Hardness, with all hypotheses checked

The finite theorem needed here is Proposition 11 of [Bernreiter, Dvořák, Rapberger, and Woltran](https://arxiv.org/html/2204.13305v1#S6): exact claim-set verification under Reduction \(1\) is \(\Sigma_2^{\mathrm P}\)-complete for preferred, semi-stable, and stage semantics, even with transitive preferences.

Its hypotheses match this task:

• The original framework is well-formed: equal claims have identical outgoing attacks.
• Preferences are asymmetric and may be restricted to transitive relations.
• Reduction \(1\) retains precisely those attacks \((t,u)\) for which \(u\not\succ t\).
• Verification asks whether an extension has exactly the prescribed claim set.

Here is the explicit reduction to the society representation. Given such a finite instance with argument set \(A=\{a_1,\ldots,a_n\}\), use one type per argument and copy its claims, attacks, preferences, and target. Assign positive rational masses summing to one.

This can even be done with dyadic masses. For \(n\geq2\), put \(k=\lceil\log_2 n\rceil\) and set
\[ \mu_{a_i}=2^{-k}\quad(1\leq i<n), \qquad \mu_{a_n}=\frac{2^k-n+1}{2^k}. \]
The last numerator is positive because \(2^k\geq n\). All masses have \(O(\log n)\)-bit encodings, and their sum is one. For \(n=1\), assign mass one.

The construction preserves all structural restrictions, has \(\tau=n\), and adds only \(O(n\log n)\) bits. Its finite reduced graph is unchanged. Section 1 proves that the source and constructed instances have the same answer. This establishes \(\Sigma_2^{\mathrm P}\)-hardness for each of the three fixed semantics.

3. Membership in \(\Sigma_2^{\mathrm P}\)

For \(S\subseteq T\), write
\[ S^+=\{u\in T:\exists t\in S,\ (t,u)\in R_1\}, \qquad \rho(S)=S\cup S^+. \]

A set is conflict-free if it contains no attack between its members. It is admissible if it is conflict-free and, whenever \(u\) attacks a member of \(S\), some member of \(S\) attacks \(u\). These properties, the range \(\rho(S)\), and the equality \(q(S)=C\) are computable in polynomial time.

The three extension conditions are:

• Preferred: \(S\) is admissible, and no admissible \(U\) satisfies \(S\subsetneq U\).
• Semi-stable: \(S\) is admissible, and no admissible \(U\) satisfies \(\rho(S)\subsetneq\rho(U)\).
• Stage: \(S\) is conflict-free, and no conflict-free \(U\) satisfies \(\rho(S)\subsetneq\rho(U)\).

For semi-stable semantics, this is the standard equivalent formulation using admissible sets. To justify the equivalence with complete-set range maximization: the fundamental lemma says that adding a defended argument to an admissible set preserves admissibility. A defended argument outside an admissible \(S\) cannot belong to \(S^+\), since that would force an attack between members of \(S\). Thus adding any missing defended argument strictly enlarges the range. Range-maximal admissible sets are therefore complete. Moreover, every admissible set extends to a maximal admissible set by finiteness; the same lemma makes that extension complete. Hence maximizing ranges over complete or admissible sets gives identical results.

Each decision problem consequently has the form
\[ \exists S\subseteq T\ \forall U\subseteq T:\ P_\sigma(S,U), \]
where \(P_\sigma\) is polynomial-time decidable: it checks the target claims, the appropriate base property, and the absence of the indicated domination by \(U\). Both quantified subsets have \(\tau\)-bit encodings. This proves membership in \(\Sigma_2^{\mathrm P}\), completing the classification.

4. Explicit running times

After polynomial-time preprocessing of the input, use indexed Boolean matrices for the relations. Testing conflict-freeness or admissibility and computing a range takes \(O(\tau^2)\) elementary operations; testing the target claim set takes \(O(\tau+m)\).

A direct enumeration of all candidate–competitor pairs gives a polynomial-space algorithm with
\[ O\!\left(4^\tau(\tau^2+m)+\operatorname{poly}(L)\right) \]
elementary operations.

The exponential factor can be improved by a Boolean superset computation. For a Boolean function \(f\) on subsets of \(T\), initialize \(H(B)=f(B)\). For each \(t\in T\), update every \(B\) not containing \(t\) by
\[ H(B)\leftarrow H(B)\lor H(B\cup\{t\}). \]
After processing a set \(J\) of coordinates, the invariant is
\[ H(B)=\bigvee_{B\subseteq D\subseteq B\cup J}f(D). \]
It follows inductively from the update, and at termination gives
\[ H(B)=\bigvee_{D\supseteq B}f(D). \]
Thus a strict marked superset of \(B\) exists exactly when
\[ \bigvee_{t\notin B}H(B\cup\{t\}) \]
is true.

Apply this as follows:

• For preferred semantics, mark precisely the admissible subsets.
• For semi-stable semantics, mark precisely the ranges attained by admissible subsets.
• For stage semantics, mark precisely the ranges attained by conflict-free subsets.

Enumerate candidates again and accept precisely when the candidate has claims \(C\), satisfies its base condition, and its subset or range has no strict marked superset. Competitors must include all base-valid subsets, regardless of their claims.

Enumeration costs \(O(2^\tau(\tau^2+m))\) operations, and the superset computation costs \(O(\tau2^\tau)\). Hence all three problems admit
\[ O\!\left(2^\tau(\tau^2+m)+\operatorname{poly}(L)\right) \]
elementary operations with exponential storage, or \(2^\tau\operatorname{poly}(L)\) time when bit costs are included. This is polynomial for fixed \(\tau\), but does not provide a polynomial bound when \(\tau\) is unrestricted.

⟨structured verdict parsed — rendered above⟩

The claimed complexity classification is correct in substance: for each fixed \(\sigma\in\{\mathrm{prf},\mathrm{sem},\mathrm{stg}\}\), the continuous problem is \(\Sigma_2^{\mathrm P}\)-complete and therefore \(\mathrm{NP}\)-hard. The semantic equivalence, membership argument, and exponential-time algorithm withstand verification. There is one minor boundary-case omission in the stated reduction.

• Reduction from measurable sets to support subsets: correct.

For every \(S\subseteq T\), the finite union \(E_S\) is measurable. Since the intervals form a partition and every mass is positive, its intersection with \(I_t\) has positive measure exactly when \(t\in S\). Thus \(S(E_S)=S\), including when \(S=\varnothing\).

Conversely, the support of any measurable \(E\) is a subset of \(T\). Null modifications preserve every intersection measure, so the support is well-defined under the stipulated equivalence modulo null sets.

Acceptance is defined directly through this support. Consequently, the displayed existential equivalence follows exactly, without any further argument about attacks between individual points. The conclusion that masses and interval placement do not affect the answer is justified.

• The cited hardness theorem and its hypotheses: verified.

Proposition 11 states the required \(\Sigma_2^{\mathrm P}\)-completeness for exact claim-set verification under Reduction \(1\), for all three semantics, including the restriction to transitive preferences. The source definitions also agree with the task’s well-formedness requirement, asymmetric preferences, attack deletion rule, and projection of extensions to claim sets. See [Proposition 11 and the framework definitions](https://arxiv.org/html/2204.13305v1).

Copying one argument to one type preserves claims, attacks, asymmetry, transitivity, and equal-claim outgoing attacks. The reduced graph is therefore unchanged.

For \(n\geq2\), the mass construction is valid: the final numerator is positive, and the total numerator is
\[ (n-1)+(2^k-n+1)=2^k. \]
Hence the masses sum to one. Their encoding lengths and total additional encoding cost have the claimed bounds. The \(n=1\) case is explicitly covered.

Minor issue: the construction does not cover \(n=0\). The cited finite-framework definition permits an empty argument set, whereas the society’s mass normalization requires nonempty support. This does not undermine the hardness result, but the reduction’s stated domain needs clarification.

Minimum clarification: explicitly restrict the source reduction to a nonempty hard family, or specify how an empty source instance is handled.

• Extension conditions and membership: correct.

The preferred condition uses inclusion maximality among admissible sets. The stage condition uses range maximality among conflict-free sets. Both match standard semantics.

The semi-stable condition using admissible sets is also valid. The fundamental lemma is stated in the form needed: adding an argument defended by an admissible set preserves admissibility. Its hypotheses are satisfied in both applications.

The assertion that a missing defended argument cannot already be attacked by \(S\) is sound: defense against an attacker belonging to \(S\) would require an attack between members of \(S\), contradicting conflict-freeness. Thus adding such an argument strictly enlarges the range.

Finiteness supplies inclusion-maximal admissible extensions, and range is monotone under set inclusion. These facts justify the equivalence between range maximization over admissible and complete sets.

The existential subset and universal competitor each require \(\tau\) bits. Base validity, claim equality, and strict domination are polynomial-time predicates. Competitors are unrestricted by their claims, as required. The resulting quantified formulation establishes membership in \(\Sigma_2^{\mathrm P}\).

• Running-time claims: correct.

With indexed relation matrices, conflict-freeness and range computation take \(O(\tau^2)\) operations. Admissibility can also be checked within that bound by computing the attacked set and checking attackers of accepted arguments. Claim equality takes \(O(\tau+m)\).

Enumerating all candidate–competitor pairs therefore supports the stated
\[ O\!\left(4^\tau(\tau^2+m)+\operatorname{poly}(L)\right) \]
bound with polynomial working space.

The Boolean superset computation is valid. During a coordinate update, the source entry contains that coordinate and is not itself modified in that pass. The stated invariant therefore holds for the in-place updates.

The strict-superset test excludes equality correctly. Marking admissible subsets for preferred semantics, and attainable ranges for semi-stable and stage semantics, supplies exactly the relevant competitors. Multiple subsets attaining the same range cause no problem.

The resulting bound
\[ O\!\left(2^\tau(\tau^2+m)+\operatorname{poly}(L)\right) \]
and its bit-cost formulation \(2^\tau\operatorname{poly}(L)\) are justified.

• Edge cases and overall adjudication.

Empty accepted supports, empty targets, self-attacks, and claims with no supporting type are handled by the definitions and exhaustive algorithm. Valid society inputs necessarily have \(\tau\geq1\).

The proof establishes hardness for each fixed semantics, rather than relying on semantics being part of the variable input. Its polynomial-time implication is stated correctly as conditional on \(\mathrm P=\mathrm{NP}\). No major gap or false central step was found.

⟨structured verdict parsed — rendered above⟩