Answer: \(\mathsf{NP}\)-hard, even when \(\tau=1\), \(C=\varnothing\), and \(|W|=2\), with weights \(2\) and \(1\). A polynomial-time algorithm would imply \(\mathsf P=\mathsf{NP}\).
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor any WAF ⟨A, R, C, W⟩with |W| = n, the problems CAmcS and SAmcS are: - ∆P 2 [log n]-complete for any semantics S ∈{co, st}, - ∆P 3 [log n]-complete for S ∈{pr, sst}. Stratified Weak Constrained AFs In this section we consider WAFs where weak constraints define a partial order. The partial order on the set W of weak constraints is defined by partitioning W into strata W1, . . . , Wn (with n ≥1) so that weak constraints in a stra- tum i have higher priority than those in a stratum j > i. Definition 11.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given an argumentation framework \(\langle A,R\rangle\), strong constraints \(C\), weak constraints \(W\), target argument \(a\), and a finite support \(T\) of types with binary-rational masses \(\mu_t\) and binary-rational preference weights \(w_{t,\omega}\) over \(W\), let \(\mathcal{P}_C\) be the preferred extensions satisfying \(C\), and define \(U_\mu(E)=\sum_{t\in T}\mu_t\sum_{\omega\in W}w_{t,\omega}\mathbf{1}[E\models\omega]\). Decide whether some utility-maximizing extension in \(\mathcal{P}_C\) contains \(a\).
Given a finite Dung argumentation framework \(\langle A,R\rangle\), a target \(a\in A\), and finite sets \(C,W\) of explicitly encoded strong and weak constraints, put \(m=|A|\).
Strong constraints have form \(\varphi\Rightarrow v\) or \(v\Rightarrow\varphi\); weak constraints have form \(\varphi\to v\) or \(v\to\varphi\), where \(v\in\{\mathsf f,\mathsf u,\mathsf t\}\) and \(\varphi\) is built from arguments using \(\land,\lor,\neg\). Assume \(C\) is jointly satisfiable by a three-valued assignment.
For an extension \(E\), arguments in \(E\) have value \(\mathsf t\), arguments attacked by \(E\) have value \(\mathsf f\), and remaining arguments have value \(\mathsf u\). Evaluate conjunction and disjunction by minimum and maximum in \(\mathsf f<\mathsf u<\mathsf t\); negation swaps \(\mathsf f,\mathsf t\) and fixes \(\mathsf u\). Either implication is satisfied exactly when its body's value is at most its head's value.
Let \(\mathcal P_C\) consist of the standard preferred extensions of \(\langle A,R\rangle\) satisfying every constraint in \(C\); preferredness is determined before filtering by \(C\).
A society is given by its support: a list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau=|T|\) is the support size, not the number of possible types. Each type supplies a nonnegative binary-rational weight \(w_{t,\omega}\) for every \(\omega\in W\), with no normalization of weights.
Define \(U_\mu(E)=\sum_{t\in T}\mu_t\sum_{\omega\in W}w_{t,\omega}\mathbf 1[E\models\omega]\). Decide whether some maximizer over \(\mathcal P_C\) contains \(a\); all tied maximizers qualify, and the answer is no if \(\mathcal P_C=\varnothing\). Let \(L\) be the total input bit length; state running times in \(m,\tau,L,|R|,|C|,|W|\).
Is this mass-weighted preferred-acceptance problem solvable in polynomial time, or is it NP-hard?
For the discrete unweighted version, credulous acceptance among preferred extensions maximizing the number of satisfied weak constraints is \(\Delta^P_3[\log n]\)-complete, where \(n=|W|\). [Source](https://cdn.aaai.org/ojs/16768/16768-13-20262-1-2-20210518.pdf).
No result settling the exact mass-weighted formulation was verified.
The problem is NP-hard, even with one type, no strong constraints, and exactly two weak constraints with weights \(2\) and \(1\). Consequently, a polynomial-time algorithm would imply \(\mathsf P=\mathsf{NP}\).
The proof below is independent of the complexity classification supplied for the unweighted version.
Let \(F(x_1,\ldots,x_n)\) be a Boolean formula whose satisfiability is to be decided. Construct the argumentation framework with
\(A=\{x_i,\bar x_i:1\leq i\leq n\}\cup\{a,b\}\)
and attacks
\(R=\{(x_i,\bar x_i),(\bar x_i,x_i):1\leq i\leq n\}\cup\{(a,b),(b,a)\}.\)
Here \(\bar x_i\) is the name of a separate argument. The framework consists of disjoint mutually attacking pairs.
Set \(C=\varnothing\), which satisfies the promise of joint satisfiability. Use one type \(t_0\), with mass \(\mu_{t_0}=1\). Introduce the weak constraints
\(\omega_1:\mathsf t\to(a\land F(x_1,\ldots,x_n)),\qquad \omega_2:\mathsf t\to\neg a,\)
with weights \(w_{t_0,\omega_1}=2\) and \(w_{t_0,\omega_2}=1\). Negative literals in \(F\) use the formula operator \(\neg\).
Recall that a set is admissible if it is conflict-free and defends every member against every attacker. A preferred extension is an inclusion-maximal admissible set.
In this framework, a conflict-free set contains at most one argument from each pair. Every such set is admissible: the only attacker of a selected argument is its partner, and the selected argument attacks that partner.
If an admissible set omits both members of a pair, adding either member preserves conflict-freeness and hence admissibility. Conversely, a set containing exactly one member from every pair cannot be enlarged while preserving conflict-freeness. Therefore,
\(E\text{ is preferred}\iff E\text{ contains exactly one argument from each pair}.\)
Every preferred extension consequently induces a two-valued assignment: each selected argument is \(\mathsf t\), and its unselected partner is attacked and therefore \(\mathsf f\). On these assignments, the stipulated conjunction, disjunction, and negation agree with Boolean evaluation. Thus the choices from the variable pairs represent all Boolean assignments to \(F\).
Because the body of either weak constraint is \(\mathsf t\), the constraint is satisfied exactly when its head evaluates to \(\mathsf t\).
For any preferred extension \(E\):
| Selector choice | Value of \(F\) | Satisfied weak constraints | Utility |
|---|---|---|---|
| \(b\in E\) | Either value | Only \(\omega_2\) | \(1\) |
| \(a\in E\) | \(\mathsf t\) | Only \(\omega_1\) | \(2\) |
| \(a\in E\) | \(\mathsf f\) | Neither | \(0\) |
If \(F\) is satisfiable, choose its satisfying assignment and select \(a\). The resulting preferred extension has utility \(2\), the largest possible utility, and contains the target.
If \(F\) is unsatisfiable, every preferred extension containing \(a\) has utility \(0\). Preferred extensions selecting \(b\) exist and have utility \(1\), so no maximizer contains \(a\).
Hence,
\(F\text{ is satisfiable}\iff\text{some maximizing preferred extension contains }a.\)
The construction has \(m=2n+2\), \(|R|=2n+2\), \(\tau=1\), \(|C|=0\), and \(|W|=2\). Its encoding length and construction time are polynomial in the SAT input length. This proves NP-hardness under polynomial-time many-one reductions.
An exact exponential-time algorithm is also available. The binary-rational weights can first be converted to integer scores without changing maximizers.
Write the input rationals as \(\mu_t=p_t/q_t\) and \(w_{t,\omega}=r_{t,\omega}/s_{t,\omega}\), with positive denominators. Define
\(D=\left(\prod_{t\in T}q_t\right) \left(\prod_{t\in T}\prod_{\omega\in W}s_{t,\omega}\right)\)
and, for each weak constraint,
\(B_\omega=\sum_{t\in T}p_t r_{t,\omega}\frac{D}{q_t s_{t,\omega}}.\)
Each \(B_\omega\) is a nonnegative integer, and
\(D\,U_\mu(E)=\sum_{\omega\in W}B_\omega\mathbf 1[E\models\omega].\)
The bit length of \(D\) is at most the sum of the input denominator lengths, hence is \(O(L)\). Also,
\(B_\omega=D\sum_t\mu_t w_{t,\omega}\leq D\max_t w_{t,\omega}.\)
Every input weight is at most \(2^L\), so every coefficient and every total score has \(O(L)\) bits. Elementary binary arithmetic computes the coefficients in time \(O(\tau(|W|+1)L^2)\).
Now enumerate all \(2^m\) subsets of \(A\), recording whether each is admissible. An admissibility check takes \(O(m+|R|)\) elementary graph operations: check conflict-freeness, compute the arguments attacked by the set, and verify that every attacker of a member belongs to this attacked set.
To determine preferredness efficiently, let \(G(S)\) mean that an admissible superset of \(S\) exists, allowing equality. Compute, in decreasing order of cardinality,
\(G(S)=\operatorname{Adm}(S)\lor\bigvee_{x\in A\setminus S}G(S\cup\{x\}).\)
This recurrence is correct because every strict superset of \(S\) contains some \(S\cup\{x\}\). Therefore,
\(S\text{ is preferred}\iff \operatorname{Adm}(S)\land \neg\bigvee_{x\in A\setminus S}G(S\cup\{x\}).\)
This step uses \(O(m2^m)\) Boolean operations. Crucially, it determines preferredness before checking the strong constraints.
Finally, evaluate \(C\) on each preferred extension, discard extensions violating a strong constraint, and compute the integer scores of the remaining extensions. Track the largest score and whether any extension attaining it contains \(a\). If none survives, return no.
Including formula evaluation, binary arithmetic, and subset handling, a conservative deterministic running-time bound is
\(O\!\left(\tau(|W|+1)L^2+ 2^m\bigl(m+|R|+|C|+|W|+L\bigr)L^2\right).\)
Thus the requested hardness question is settled, while exact computation remains possible by enumeration.
⟨structured verdict parsed — rendered above⟩
The output correctly establishes NP-hardness for the stated mass-weighted problem. The reduction and the exact enumeration algorithm are sound. I found no major or minor issues requiring repair.
The reduction uses precisely the intended problem: standard preferred extensions are determined before strong-constraint filtering, and maximization uses the given mass-weighted utility.
Both weak constraints have the permitted form \(v\to\varphi\), with \(v=\mathsf t\). The formula \(F\) is interpreted using the permitted Boolean connectives, and \(\bar x_i\) denotes a separate argument rather than formula negation. The selector arguments \(a,b\) are understood as fresh names.
The remaining input conditions hold: \(C=\varnothing\) satisfies the strong-constraint promise; the single mass is positive and sums to \(1\); and weights \(2,1\) are nonnegative binary rationals. No weight normalization is assumed or needed.
The admissibility argument is correct. Conflict-freeness permits at most one argument from each mutually attacking pair. Each selected argument attacks its sole attacker, so every conflict-free set defends all its members.
If a pair is entirely omitted, either member can be added without introducing a conflict with any other pair. The enlarged set remains admissible. Conversely, choosing exactly one member from every pair prevents any conflict-free enlargement.
Thus the stated equivalence between preferred extensions and selections of exactly one member per pair is valid. This also establishes that preferred extensions exist in every constructed instance.
Every argument receives either \(\mathsf t\) or \(\mathsf f\): selected arguments are true, and their unselected partners are attacked and therefore false. No argument remains undecided.
On these two-valued assignments, the stipulated minimum, maximum, and negation operations agree with Boolean conjunction, disjunction, and negation. The independent variable-pair choices therefore represent every Boolean assignment to \(F\). The use of \(\neg x_i\) inside \(F\) is consistent with this interpretation.
The implication test is applied correctly. Since its body is \(\mathsf t\), either weak constraint is satisfied exactly when its head is \(\mathsf t\).
Every row of the utility table is correct:
In particular, utility \(3\) is impossible because the two constraints cannot both be satisfied.
If \(F\) is satisfiable, its satisfying assignment can be combined with selecting \(a\), yielding a preferred extension of maximum utility \(2\).
If \(F\) is unsatisfiable, every preferred extension containing \(a\) has utility \(0\), while extensions selecting \(b\) exist and have utility \(1\). Hence no maximizing extension contains \(a\).
This verifies both directions of the claimed equivalence. Ties cause no difficulty under the task’s acceptance convention.
The counts \(m=2n+2\), \(|R|=2n+2\), \(\tau=1\), \(|C|=0\), and \(|W|=2\) are correct. The formula is included once, and the remaining construction has linear size in the number of variables. The encoding length and construction time are polynomial in the SAT input length.
Consequently, the NP-hardness claim follows. The statement that a polynomial-time algorithm would imply \(\mathsf P=\mathsf{NP}\) is appropriately conditional.
The denominator \(D\) is positive and divisible by each product \(q_t s_{t,\omega}\), including when the numerical denominators share factors. Therefore every displayed coefficient \(B_\omega\) is a nonnegative integer.
Expanding the definition verifies the claimed identity between the integer score and \(D\,U_\mu(E)\). Multiplication by the same positive constant preserves all comparisons and ties.
The bit-length bounds also hold. The denominator product has \(O(L)\) bits. The coefficient bound uses precisely the positive masses summing to \(1\), and does not require normalized weights. Summing at most \(|W|\) coefficients adds at most \(O(\log(|W|+1))\) bits, which is absorbed by \(O(L)\) for explicitly encoded input.
The stated coefficient-computation bound is consistent with elementary binary multiplication, division, and addition on \(O(L)\)-bit integers.
The admissibility check correctly tests conflict-freeness and whether the set attacks every attacker of each selected member. Its graph-operation bound is valid with indexed arguments and membership arrays.
The recurrence for \(G(S)\) correctly detects any admissible superset, allowing equality. Decreasing cardinality ensures that all referenced values have already been computed.
The subsequent preferredness test correctly excludes every strict admissible superset, including supersets reached through intermediate sets that themselves are inadmissible. Its \(O(m2^m)\) Boolean-operation bound is valid.
Strong constraints are checked only after preferredness, as required. Formula evaluation, integer-score comparison, tied-maximizer tracking, and the empty-filtered-family case are all handled correctly.
The displayed bound accounts conservatively for preprocessing, subset enumeration, graph checks, formula evaluation, and arithmetic. Total explicitly encoded formula size is covered by \(L\); the additional \(L^2\) factor safely covers the stated arithmetic and subset-handling costs.
The output settles the requested hardness question and supplies a valid exact exponential-time algorithm. It does not claim an unsupported completeness classification.
No additional clarification is needed to verify the argument.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.