| paper | d4-conf-ecai-2010-0007 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
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}\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 2 (solution equivalence)
statement extracted from the paper’s text layer
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\).
A society is a distribution \(\mu\) over complete supporter profiles \(q_t\); each attack's per-capita strength is the mass-weighted sum \(W_\mu(a,b)\). The decision variables are argument-inclusion indicators \(z_a\in\{0,1\}\), and the task is to find all feasible extensions, with no separate optimization objective.
The induced attack-weight vector is a sufficient statistic already accepted by the paper, so supporter-type composition adds no distinct computational structure; the proponent acknowledges this compression but does not show that type composition affects the extension computation.
fatal: False
Covers Theorem 2's SCSP computation of \(\alpha\)-admissible, \(\alpha\)-complete, or \(\alpha\)-stable extensions using population-derived attack weights; it does not continuize the other semiring interpretations, the extension-property results, or the future clustering proposal.
The strongest honest mirror is a narrow one: the computation of weighted Dung extensions when attack strengths come from the mass of people who support those attacks. That population interpretation is already suggested by the paper, which gives “votes in support of the associated attack” as one reading of attack weights.
My anchor is Theorem 2 (solution equivalence), stated in this paper. It is a computational formulation result, not a theorem about running time: the paper gives no named NP-hardness, polynomial-time, or parameterized-complexity result. Theorem 2 says that, for the SCSP \(P\) constructed from a semiring-based argumentation framework, its \(\alpha\)-consistent solutions correspond to all \(\alpha\)-admissible extensions when \(P\) uses the conflict-free and admissible constraints; to all \(\alpha\)-complete extensions when it also uses the complete constraints; and to all \(\alpha\)-stable extensions when it uses the conflict-free and stable constraints. This theorem is presented here, drawing on Dung’s semantics for background. It qualifies as an anchor because the paper uses the encoding to compute the underlying extensions.
The corresponding continuous problem could be called Mass-Supported \(\alpha\)-Extension. An instance has a finite set of arguments \(\mathrm{Args}\), a finite set of possible attack pairs \(E\), and a finite set \(T\) of supporter types. Each type \(t\) has rational mass \(\mu_t\), with \(\sum_{t\in T}\mu_t=1\), and a complete profile \(q_t:E\to\mathbb{Q}_{\ge 0}\) specifying how much that type contributes to each attack. The resulting attack strength is
\[ W_\mu(a,b)=\sum_{t\in T}\mu_t q_t(a,b). \]
Given a rational tolerance \(\alpha\) and a requested semantics—\(\alpha\)-admissible, \(\alpha\)-complete, or \(\alpha\)-stable—compute all sets \(B\subseteq\mathrm{Args}\) satisfying that semantics under \(W_\mu\). In the weighted semiring, the conflict-budget condition is that the total internal attack cost is at most \(\alpha\); defense and stability follow the paper’s definitions using the derived attack strengths. The decision variables are the argument-inclusion indicators \(z_a\in\{0,1\}\). There is no separate optimization objective in the anchor: the task is to find the feasible extensions, or enumerate all of them. The SCSP is a proposed way to solve that underlying problem, not the problem being mirrored.
A plausible regime is a large public deliberation platform with many users responding to a finite set of recurring claims. Users who endorse the same attack relationships with the same strengths form one type; their mass is their share of the population. The population can be very large while the number \(\tau=|T|\) of distinct profiles stays moderate. This fits the paper’s own vote-support interpretation, and the authors could recognize it as a continuous source for the weighted attacks they study. The arguments and the extensions remain finite and discrete; the continuum is the population supplying the attack weights.
For this mirror, I expect hardness to transfer wherever the corresponding finite weighted-extension problem is hard: a one-type population with \(\mu_t=1\) can encode any specified attack-strength vector through \(q_t\). That is an embedding argument, not a complexity result established by this paper. Theorem 2 supplies a computation framework, but no tractability guarantee. The anchor covers the paper’s extension-computation results in Section 5, not its full claim of a common framework for every semiring or its future clustering proposal.
Two follow-up questions arise: how the extension set changes as the masses vary, and whether restricted supporter profiles or attack graphs yield efficient computation in parameters such as \(|\mathrm{Args}|\), \(\tau\), and input bit length.
The weak point is that attack weights in the paper are already aggregate values. Expressing vote totals as population shares may look like a change of units, and the extension itself is not fractional. The case survives because the paper explicitly gives votes as a source of attack weights: the distribution over supporter types makes that population a first-class input to the extension problem, rather than merely relabeling a fractional outcome or a noisy finite profile.
The proponent has one anchor: Theorem 2. It proves that solutions of a constructed soft constraint problem correspond to weighted argumentation extensions. It does not give a running-time bound, an algorithm for the underlying problem, or a complexity classification. The paper’s computational contribution is the encoding itself. So there is no named complexity result here for ChoCo to continuize; at most, the mirror would ask how to compute extensions from a population-derived input.
The proposed supporter population is plausible: the paper itself mentions votes supporting attacks. But for any supporter types \(t\), the extension computation depends on their distribution only through the attack weights
\[
W_\mu(a,b)=\sum_t \mu_t q_t(a,b).
\]
Once those weights are fixed, the distribution has no further effect. Two societies with different type profiles but the same \(W_\mu\) produce exactly the same extensions. If type contributions \(q_t\) are unrestricted, one type can encode any weight vector. Even if each person only supports or does not support each attack, a distribution over such profiles supplies aggregate edge weights; the computation still reduces to the weighted AF input. The number and composition of supporter types add no relevant structure.
That is the central difficulty for this mirror. It does not reveal a population-driven computational problem beyond the weighted framework already studied in the paper. The authors could reasonably recognize the vote-share interpretation, but the continuous society is only a way to generate the same edge weights. This is not an objection that high multiplicity has already been studied elsewhere; it is that, in this model, the population is mathematically quotiented out before the computation begins.
A stronger population question might ask how extension sets change as support shifts between types, or what recruitment effort changes whether an argument is accepted. The first pulls the existing weighted-AF answer back through the map \(\mu\mapsto W_\mu\). The second needs a new intervention model, with costs or constraints on changing the population. Either could be worth studying, but neither is a computational result of this paper: the paper has no decision variable over supporters and no manipulation or robustness objective.
Putting the population on the arguments themselves is not a clean escape. Arguments are graph nodes whose individual attack relations determine admissibility and stability; duplicate claims are not automatically interchangeable if their graph neighborhoods differ. An atomless argument population would require new semantics for whether an outside argument is “attacked” by an accepted set, and whether zero-mass arguments can affect defense or consistency. Those may be interesting foundations, but they change the object being computed rather than continuize the paper’s extension computation.
The negative case is strongest against the proposed vote-support mirror, and weaker as a universal claim. A study of how population composition moves attack weights and changes extensions might still interest argumentation researchers. What is missing is a clear reason it belongs in this continuization programme: in the paper’s model, that population composition collapses to weights the framework already takes as input.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.