| paper | d4-journals-jair-2024-0058 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-hard; more precisely, \(\#\!\cdot\!\mathrm{NP}\)-complete under parsimonious reductions. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 7(1)
statement extracted from the paper’s text layer
Given a finite set of supported argument types \(T\), a type-uniform attack relation \(R\subseteq T\times T\), a rational distribution \(\mu\) with \(\mu_t>0\) and \(\sum_{t\in T}\mu_t=1\), a target type \(c^\star\), and a projection \(P\subseteq T\), count the distinct projected mass profiles \((q_t)_{t\in P}\) induced by stable sets \(S\subseteq T\) containing \(c^\star\), where \(S\) is conflict-free, attacks every type outside \(S\), and \(q_t=\mu_t\) for \(t\in S\) and \(q_t=0\) otherwise.
A society consists of people submitting types from \(T\), with mass \(\mu_t\) for each type and attacks determined by \(R\). The decision variable is a stable accepted type set \(S\); its accepted mass is \(q_t\in\{0,\mu_t\}\). The objective is to count distinct restrictions \((q_t)_{t\in P}\) among stable sets containing \(c^\star\).
The application treats argument templates as person-types, a population interpretation the paper itself does not supply; the proposed mirror’s recognition by the authors rests on that consultation scenario.
fatal: False
The mirror covers the stable-semantics component of Theorem 7(1); it leaves the other semantics, classical extension-counting results, and treewidth algorithms and lower bounds outside its scope.
My lead is Mass-Projected Stable Credulous Counting. Consider a large consultation where people submit arguments from a finite catalogue of templates. A type \(t\) is one template together with its complete attack behavior: everyone of type \(t\) makes the same argument and attacks and is attacked by the same types. The society is a distribution \(\mu\) over the supported types, with \(\mu_t>0\) and \(\sum_t\mu_t=1\). Millions of submissions can then be represented by a modest number \(\tau\) of types and their rational mass fractions.
The decision object is a set \(S\subseteq T\) of accepted argument types. It is stable when \((S\times S)\cap R=\varnothing\), and every \(t\notin S\) is attacked by some \(s\in S\). Its accepted population profile is \(q_t^S=\mu_t\) for \(t\in S\), and \(q_t^S=0\) otherwise. Given a target type \(c^\star\) and a projection set \(P\subseteq T\), the problem asks for the exact number of distinct profiles \((q_t^S)_{t\in P}\) arising from stable \(S\) with \(c^\star\in S\). Each profile counts once. The masses are binary rationals; the answer is an integer.
The anchor is Theorem 7(1), proved in this paper. For stable semantics, \(\#\mathrm{PCred}_{\mathrm{stable}}\) takes an argumentation framework, a projection set \(P\), and an argument \(a\), and outputs the number of distinct sets \(S\cap P\) over stable extensions \(S\) containing \(a\). The theorem states that this problem is \(\#\!\cdot\mathrm{NP}\)-complete via parsimonious reductions. Lemma 5 proves membership and Lemma 6 proves hardness. The mass-profile problem asks the same question at type level: since every supported type has positive mass, its projected mass profile identifies exactly which types in \(P\) are accepted.
There is a concrete high-multiplicity interpretation behind that correspondence. Replace each type by many individual copies, and let every copy of \(t\) attack every copy of \(u\) exactly when \((t,u)\in R\). Stable extensions of this expanded framework contain either all copies of a type or none: if they included some but omitted others, an omitted copy would be unattacked. Thus stable extensions of the type graph correspond to stable extensions of the expanded graph, and projection to type blocks gives precisely the profiles above. A population can have \(N=\tau^2\) agents, with \(\tau\) agents per type, while its compressed description still has only \(\tau\) types.
I expect this mirror to be Class B: hardness transfers. Any instance from Theorem 7 maps to the mass-profile problem by making one type per argument, preserving attacks, target, and projection, and assigning positive rational masses. The correspondence preserves the answer exactly. Replicating each type’s agents preserves it too. So the hardness lives in the attack structure over types, not in how many named individuals instantiate them.
I think the authors could recognize this as their stable projected-counting problem in a high-multiplicity regime, provided the application really has type-uniform attacks and the question concerns accepted argument templates. The mirror covers this one stable projected-counting result; it does not claim to continuize every semantics or every argumentation framework in the paper.
The weak point is that the masses label the counted profiles but do not change how many there are: the stable semantics acts on whole argument types. Someone looking for mass-sensitive argumentation semantics could regard this as an AF with a population distribution attached. I think the case still holds for the stated regime: repeated identical argument instances are naturally represented by one type, and the problem asks how many projected population-level acceptance patterns are stable.
A useful next question is whether the same type-level projection remains a faithful high-multiplicity mirror for the paper’s other semantics, especially the range-maximal ones. The answer may differ depending on whether one counts argument types or individual copies.
Theorem 7(1) is a real anchor: the paper proves that \(\#\mathrm{PCred}_{\mathrm{stable}}\) is \(\#\!\cdot\mathrm{NP}\)-complete. The strongest objection is to whether the proposed lift makes that a continuous-population problem.
In the paper, vertices are arguments, not people. To interpret repeated submissions as a population, lift each type-level attack \(s\to t\) to an attack between every pair of individuals of those types. Under the natural mass version of stable semantics, an accepted set must be conflict-free, and every unaccepted individual must be attacked by someone accepted. These conditions force each type’s accepted mass \(q_t\) to be either \(0\) or \(\mu_t\). If \(0<q_t<\mu_t\), stability requires a selected type \(s\) to attack the unaccepted part of \(t\); the same type-level attack then reaches the accepted part, violating conflict-freeness. The finite clone construction has the same all-or-none property.
So the proposed profiles \((q_t)_{t\in P}\) are binary choices labelled by the masses. They do not describe fractional acceptance of a population. Counting individual-level extensions in a literal continuum instead gives an uncountable family of subsets, outside the paper’s integer counting problem. Allowing fractional acceptance would require a new rule for how attacks behave between masses; making attacks depend on thresholds or aggregate strength would change the stable semantics being mirrored.
There is still a weakness in this negative case: the type-level formulation is precise, and the authors could recognize it as stable projected counting on a weighted encoding of an AF. Its computational question is well-posed. The argument against it is that the continuous population contributes no fractional decision object under the faithful lift; the mirror is a population interpretation of the original graph problem. If that interpretation alone counts as worthwhile continuization, this anchor survives.
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.