Answer: All three enumeration problems are \(\mathrm{NP}\)-hard in the stated sense, already for \(\tau=1\), \(\alpha=0\), and unit attack weights. For each semantics, output-polynomial enumeration is possible if and only if \(\mathrm P=\mathrm{NP}\).
Theorem 2 (solution equivalence) — class: other
PDF text-layer excerpt — equations and symbol order may be approximateGiven an AFS = ⟨Args, R, W, S⟩and the corresponding SCSP P, the α con- sistent solutions of P corresponds to all the: • α-admissible extensions by using conflict-free and admissible con- straints. • α-complete extensions by using conflict-free, admissible and com- plete constraints. • α-stable extensions by using conflict-free and stable constraints.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite argument set \(\mathrm{Args}\), possible attack pairs \(E\), supporter types \(T\), rational masses \(\mu_t\ge 0\) summing to \(1\), and per-capita attack contributions \(q_t:E\to\mathbb{Q}_{\ge 0}\), form \(W_\mu(a,b)=\sum_{t\in T}\mu_t q_t(a,b)\). For a rational tolerance \(\alpha\) and a selected semantics among \(\alpha\)-admissible, \(\alpha\)-complete, and \(\alpha\)-stable, compute all sets \(B\subseteq\mathrm{Args}\) satisfying that semantics under the weighted semiring definitions and attack strengths \(W_\mu\).
Let \(m=|\mathrm{Args}|\), with finite \(\mathrm{Args}\), and let \(E\subseteq\mathrm{Args}^2\) be possible attacks; self-attacks are allowed.
A society is given by its support: the list of \(\tau\) types with positive binary rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
Each type supplies an explicit function \(q_t:E\to\mathbb Q_{\ge0}\). Set \(W(a,b)=\sum_t\mu_tq_t(a,b)\) on \(E\), and \(W(a,b)=0\) elsewhere; the actual attack relation is \(R=\{(a,b):W(a,b)>0\}\).
Use the Weighted semiring \(\langle\mathbb R_{\ge0}\cup\{\infty\},\min,+,\infty,0\rangle\). Write \(W(B,C)=\sum_{b\in B,c\in C}W(b,c)\) and \(W(B,a)=W(B,\{a\})\); empty sums are \(0\).
Given \(\alpha\in\mathbb Q_{\ge0}\), a set \(B\subseteq\mathrm{Args}\) is \(\alpha\)-conflict-free when \(W(B,B)\le\alpha\). It defends \(b\) when every \(a\) with \((a,b)\in R\) satisfies \(W(B,a)>W(a,b)\).
It is \(\alpha\)-admissible when it is \(\alpha\)-conflict-free and defends every member; \(\alpha\)-complete when additionally every argument it defends belongs to it; and \(\alpha\)-stable when it is \(\alpha\)-conflict-free and \(W(B,c)>0\) for every \(c\notin B\).
The input selects one of these three semantics. Enumerate all its sets without repetition, in arbitrary order. Let \(L\) be the total binary input length and \(K\) the total output length, representing sets by \(m\)-bit incidence vectors.
For each selected semantics, is enumeration possible in time polynomial in \(m,\tau,|E|,L,K\), or is it NP-hard in the sense that such a bound would imply \(\mathrm P=\mathrm{NP}\)?
Known: a soft-constraint encoding is claimed to characterize all three weighted extension families; this is a representation result, not a polynomial-time bound ([solution equivalence](https://bista.sites.dmi.unipg.it/didattica/CSP/argumentation/ecai2010.pdf)).
Classical admissible-extension enumeration is not output-polynomial unless \(\mathrm P=\mathrm{NP}\) ([enumeration complexity](https://www.ijcai.org/Proceedings/2017/0159.pdf)); it uses a different defense condition. No classification of the exact society-input problem above was located.
For each of admissible, complete, and stable semantics, an enumeration algorithm with total running time polynomial in \(m,\tau,|E|,L,K\) would imply \(\mathrm P=\mathrm{NP}\).
This hardness holds already when \(\tau=1\), \(\alpha=0\), and every actual attack has weight \(1\). Conversely, if \(\mathrm P=\mathrm{NP}\), all three families admit output-polynomial enumeration.
The proof uses the strict weighted defense condition stated in the question.
Let \(\varphi=C_1\land\cdots\land C_r\) be a \(3\)-CNF formula over \(x_1,\ldots,x_n\), with \(n,r\geq1\). This restriction preserves NP-hardness: one can append a clause on three fresh variables without changing satisfiability.
First introduce the labels
\[ \]
\(V=\{p,g\}\cup\{x_i,\neg x_i:1\leq i\leq n\}\cup\{c_j:1\leq j\leq r\}.\)
Define the following directed edges between labels:
There are no other edges. Repeated literal occurrences produce only one edge.
Replace each label \(v\) by two arguments, forming the pair \(P_v=\{v^1,v^2\}\). Replace every label edge \(u\to v\) by all four attacks from \(P_u\) to \(P_v\). Every such attack has weight \(1\).
Realize this as a society with one type: \(\tau=1\), \(\mu_1=1\), and \(q_1(e)=1\) for every \(e\in E\). Set \(\alpha=0\). Consequently, \(R=E\).
The construction has \(m=4n+2r+4\) arguments and \(|E|=O(n+r)\), and its binary input length is polynomial in the formula length.
Because weights are nonnegative and \(\alpha=0\), conflict-freeness means that no attack has both endpoints in the selected set.
Write \(\overline{\ell}\) for the literal complementary to \(\ell\), and let \(D_j\) be the set of distinct literals occurring in \(C_j\).
Call a set \(S\) of literals consistent if it contains no complementary pair. Say that \(S\) hits every clause if \(S\cap D_j\neq\varnothing\) for every \(j\).
For such an \(S\), define
\(B(S)=P_p\cup\bigcup_{\ell\in S}P_\ell.\)
Claim. The admissible sets of the constructed instance are exactly
\(\{\varnothing\}\cup\{B(S):S\text{ is consistent and hits every clause}\}.\)
Proof: necessity. Let \(B\neq\varnothing\) be admissible.
Every argument in \(P_g\) or \(P_{c_j}\) has a unit self-attack. Conflict-freeness therefore excludes all these arguments from \(B\). The attacks between complementary literal pairs also prevent \(B\) from meeting both \(P_\ell\) and \(P_{\overline{\ell}}\).
Suppose \(B\) contains a literal argument \(\ell^i\). One of its attackers is \(g^1\). Since gate arguments are excluded, the only possible selected attackers of \(g^1\) are the two arguments in \(P_p\). Thus defense of \(\ell^i\) requires
\(W(B,g^1)=|B\cap P_p|>W(g^1,\ell^i)=1.\)
Hence \(P_p\subseteq B\).
Another attacker of \(\ell^i\) is \(\overline{\ell}^{\,1}\). Its only attackers are \(P_g\) and \(P_\ell\). Therefore
\(W(B,\overline{\ell}^{\,1})=|B\cap P_\ell|>1,\)
which forces \(P_\ell\subseteq B\). Every selected literal thus appears as a full pair.
There must be a selected literal. Otherwise, the nonempty set \(B\) would contain only arguments from \(P_p\). Since \(r\geq1\), the attack \(c_1^1\to p^i\) would then be undefended: \(W(B,c_1^1)=0\).
Consequently, \(B=B(S)\) for some consistent literal set \(S\). For each clause, defense of \(p^1\) against \(c_j^1\) requires
\(W(B,c_j^1)=2|S\cap D_j|>1.\)
Thus \(S\) hits every clause.
Proof: sufficiency. Conversely, suppose \(S\) is consistent and hits every clause.
The set \(B(S)\) is conflict-free: it contains no gate or clause arguments and no complementary literals.
Every attacker \(c_j^h\) of a selected argument \(p^i\) receives counterattack weight
\(W(B(S),c_j^h)=2|S\cap D_j|\geq2>1.\)
The attackers of a selected literal argument \(\ell^i\) are precisely the gate arguments and the complementary literal arguments. For each \(h\),
\(W(B(S),g^h)=2>1\quad\text{and}\quad W(B(S),\overline{\ell}^{\,h})=2>1.\)
Thus every member is defended. Finally, \(\varnothing\) is admissible vacuously. This proves the claim.
A consistent literal set hitting every clause exists exactly when \(\varphi\) is satisfiable: extend its prescribed truth values arbitrarily to the remaining variables; conversely, the true literals of a satisfying assignment hit every clause. Hence
\(\varphi\text{ is satisfiable}\iff\text{a nonempty admissible set exists}.\)
First, \(\varnothing\) is complete. Every argument has an attacker:
Since \(W(\varnothing,a)=0\), the empty set defends no argument.
Now consider an admissible set \(B(S)\). We show that it defends no argument outside itself.
A useful observation is that if \(B\) is conflict-free and some \(b\in B\) attacks \(c\), then \(B\) cannot defend \(c\). Indeed,
\(W(B,b)=0<W(b,c),\)
so the required strict inequality against attacker \(b\) fails.
Every gate argument is attacked by a selected argument in \(P_p\). Every clause argument is attacked by a selected literal, because \(S\) hits every clause. The observation therefore excludes defense of gate and clause arguments.
For an unselected literal \(\ell\notin S\), the argument \(\overline{\ell}^{\,1}\) attacks both arguments in \(P_\ell\). Its only attackers are \(P_g\) and \(P_\ell\), neither of which meets \(B(S)\). Thus
\(W(B(S),\overline{\ell}^{\,1})=0,\)
and neither argument in \(P_\ell\) is defended.
These exhaust the arguments outside \(B(S)\). Therefore every admissible set in this construction is complete. Since completeness requires admissibility, the two families coincide. In particular,
\(\varphi\text{ is unsatisfiable}\implies \operatorname{Adm}=\operatorname{Comp}=\{\varnothing\},\)
whereas a satisfiable formula gives a nonempty complete set.
Suppose \(B\) is stable. Conflict-freeness again excludes all gate and clause arguments and prevents selecting complementary literals.
Each clause argument \(c_j^1\) lies outside \(B\), so stability requires \(W(B,c_j^1)>0\). Its possible attackers are its own clause pair and the literal pairs occurring in \(C_j\). Clause arguments are excluded, so at least one literal occurring in \(C_j\) must be selected.
The selected literals are therefore consistent and hit every clause. They extend to a satisfying assignment.
Conversely, let a satisfying assignment be given, and let \(S\) contain exactly its true literal for each variable. The set \(B(S)\) is conflict-free. Every outside argument is attacked:
Thus \(B(S)\) is stable, proving
\(\varphi\text{ is satisfiable}\iff\text{a stable set exists}.\)
The reduction has the following behavior:
| Selected semantics | Unsatisfiable formula | Satisfiable formula |
|---|---|---|
| Admissible | Exactly \(\{\varnothing\}\) | A nonempty set exists |
| Complete | Exactly \(\{\varnothing\}\) | A nonempty set exists |
| Stable | No sets | A nonempty set exists |
Because sets are represented by \(m\)-bit vectors, the total output length on an unsatisfiable formula is \(m\) for admissible and complete semantics, and \(0\) for stable semantics.
Fix any one of the three semantics. Suppose an enumerator has total running time bounded by a polynomial \(p(m,\tau,|E|,L,K)\). We may replace \(p\) by a nondecreasing polynomial upper bound.
On the constructed instance, simulate that enumerator for
\(T=p(m,1,|E|,L,m)\)
steps. This is polynomial in the formula length. Decide satisfiability as follows:
For an unsatisfiable formula, the output length is at most \(m\), so the enumerator must halt within \(T\) and output no nonempty set. The decision is therefore unsatisfiable.
For a satisfiable formula, either the enumerator has not halted, or its completed enumeration contains a nonempty set. In both cases the decision is satisfiable.
This yields a polynomial-time algorithm for \(3\)-SAT, implying \(\mathrm P=\mathrm{NP}\). Crucially, the argument requires only a total-time bound; it assumes no bound on the delay before the first output.
For completeness, suppose \(\mathrm P=\mathrm{NP}\).
Membership of a specified set in each family is decidable in polynomial time. Compute the rational weights exactly, then check conflict-freeness and the selected defense, completeness, or stability conditions. Products and sums of the binary input rationals have polynomially bounded bit length, so these checks use polynomial time.
Given a prefix of an incidence vector, the question whether some extension of that prefix belongs to the selected family is in \(\mathrm{NP}\): guess the remaining bits and perform the membership check. Under \(\mathrm P=\mathrm{NP}\), this prefix question is polynomial-time decidable.
Traverse the binary prefix tree, pruning every prefix with no valid completion. Every feasible prefix lies on the path to an output vector. If there are \(N\) outputs, there are at most \(1+mN\) feasible prefixes, and at most twice that many prefix tests. Each vector is output once. Since \(K=mN\), the total running time is polynomial in the requested parameters. The case \(m=0\) is immediate.
Thus, for every selected semantics, output-polynomial enumeration is possible if and only if \(\mathrm P=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The output proves the claimed classification for all three semantics. The construction respects the society input model, uses the specified strict defense inequality, and supports the total-time enumeration reduction. I found no mathematical gaps or false steps.
The restriction to formulas with \(n,r\geq1\) preserves satisfiability and NP-hardness: the appended clause uses fresh variables and can always be satisfied independently of the original formula.
The number of labels is \(2+2n+r\), so duplication gives exactly \(m=4n+2r+4\) arguments. There are at most \(2+4n+5r\) label edges, each producing four argument attacks. Thus the claimed bound \(|E|=O(n+r)\) is correct, including formulas with repeated literal occurrences.
The society realization is valid: its single positive mass is \(1\), all explicitly supplied attack weights are \(1\), and consequently \(R=E\). Its binary encoding has polynomial length.
With \(\alpha=0\), nonnegative unit weights make conflict-freeness equivalent to selecting no attack with both endpoints in the set. This includes self-attacks.
Every gate and clause argument has a self-attack, so none can belong to a conflict-free set. The attacks between complementary literal pairs exclude simultaneous selection from both pairs.
If \(\ell^i\) is selected, its attacker \(g^1\) must receive counterattack weight strictly greater than \(1\). The only attackers of \(g^1\) are gate and \(p\)-arguments. Since gate arguments are excluded, the stated calculation
\(W(B,g^1)=|B\cap P_p|>1\)
correctly forces both \(p\)-arguments into \(B\).
Likewise, the only attackers of \(\overline{\ell}^{\,1}\) are gate arguments and arguments in \(P_\ell\). Therefore
\(W(B,\overline{\ell}^{\,1})=|B\cap P_\ell|>1\)
forces selection of the entire literal pair.
A nonempty admissible set cannot contain only \(p\)-arguments: because \(r\geq1\), a clause argument attacks every selected \(p\)-argument and receives counterattack weight \(0\). Thus a selected literal exists, and the preceding deductions establish the claimed form \(B=B(S)\).
For every clause, defense of \(p^1\) against \(c_j^1\) requires
\(W(B,c_j^1)=2|S\cap D_j|>1\).
Distinct-literal sets \(D_j\) correctly account for repeated occurrences. The inequality is equivalent to hitting the clause.
Consistency of \(S\) ensures conflict-freeness of \(B(S)\). The proof checks every possible attacker of its members:
Every attacked member therefore satisfies the required strict inequality against every attacker. The empty set is admissible because its conflict-freeness and member-defense requirements hold vacuously.
The equivalence between satisfiability and a consistent clause-hitting literal set is justified in both directions. A consistent selection prescribes compatible truth values that extend to an assignment; the true literals of a satisfying assignment hit every clause. Thus the exact admissible-set characterization and its nonempty-existence consequence are established.
The empty set defends no argument: every argument has a positive-weight attacker, and every counterattack weight from the empty set is \(0\). The use of \(r\geq1\) for the \(p\)-arguments is explicit.
The observation concerning an attack from a member of a conflict-free set is correct. If \(b\in B\) attacks \(c\), conflict-freeness gives \(W(B,b)=0\), whereas \(W(b,c)>0\); hence defense of \(c\) fails against attacker \(b\).
This observation excludes defense of every gate and clause argument by \(B(S)\). For an unselected literal \(\ell\), the attacker \(\overline{\ell}^{\,1}\) receives no counterattack from \(B(S)\), because its only attackers are \(P_g\) and \(P_\ell\), both absent. This remains valid whether or not the complementary literal is selected.
These cases exhaust all outside arguments. Consequently every admissible set in the construction is complete, and the claimed coincidence of the two families is proved.
A stable set cannot contain gate or clause arguments or complementary literals. Every clause argument therefore lies outside it and must receive positive attack weight from a selected literal occurring in that clause. The selected literals are consistent and hit every clause, establishing satisfiability.
Conversely, the set constructed from a satisfying assignment contains both \(p\)-arguments and exactly one full literal pair per variable. The proof checks every outside argument: gates are attacked by \(P_p\), clauses by selected satisfying literals, and unselected literals by their selected complements. All these attack weights are positive.
Stable existence is therefore equivalent to satisfiability. This argument does not require stable sets to satisfy admissibility.
The unsatisfiable-instance output bounds are correct: admissible and complete enumeration output exactly one \(m\)-bit vector, whereas stable enumeration outputs nothing.
The timeout argument is valid for arbitrary output order and requires no delay guarantee. Under the assumed total-time bound, every unsatisfiable instance must halt within the chosen polynomial timeout. On a satisfiable instance, either enumeration has not halted, or its completed output contains a nonempty set. Both branches correctly identify satisfiability.
Replacing the running-time polynomial by a nondecreasing polynomial upper bound justifies using \(K=m\) also for stable instances with \(K=0\). The polynomial can be fixed as part of the resulting decision algorithm; the reduction does not need to infer it from execution.
Hence an output-polynomial enumerator for any selected semantics would give a polynomial-time algorithm for \(3\)-SAT and imply \(\mathrm P=\mathrm{NP}\).
Membership verification is polynomial-time for all three families. Exact rational products, sums, and comparisons have polynomially bounded bit lengths under the stated explicit binary encoding.
Prefix feasibility belongs to \(\mathrm{NP}\), with the remaining incidence bits serving as the certificate. Under \(\mathrm P=\mathrm{NP}\), the pruning test is therefore polynomial-time.
The prefix-tree counting argument is correct: with \(N\) outputs, feasible prefixes are contained in their length-\(m\) paths, giving at most \(1+mN\) such prefixes. Testing children of feasible prefixes, together with the root test, yields the asserted polynomial bound. Each incidence vector is reached once, preventing repetition. The bound also accommodates \(N=0\).
When \(m=0\), the empty set is the unique extension under each semantics, so the separately mentioned edge case is immediate despite its zero-bit representation.
The proof resolves the entire requested classification, including the single-type, unit-weight restriction and the conditional converse. No additional clarification is needed.
⟨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.