| paper | d4-conf-ijcai-2009-0041 |
| 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}\)-complete · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4(a)
statement extracted from the paper’s text layer
Given a finite support of argumentation-framework types \(G_t=(A_t,R_t)\), each containing a common query argument \(p\), binary-rational masses \(\mu_t\) summing to \(1\), and a rational threshold \(q\in(0,1]\), decide whether \(\sum_{t:\exists S\in E_{\mathrm{GR}^*}(G_t),\ p\in S}\mu_t\ge q\).
Each type is a complete argumentation profile \(G_t\) with mass \(\mu_t\); the objective is the total mass of types whose framework credulously accepts \(p\). This is the weighted indicator sum \(\sum_t\mu_t\,\mathbf{1}[\exists S\in E_{\mathrm{GR}^*}(G_t):p\in S]\), without needing to assign extensions to individuals.
The population statistic is a weighted batch of independent framework queries, with no shared population-level \(\mathrm{GR}^*\) semantics; the profile scenario makes that aggregation plausible but does not derive it from the paper’s semantics.
fatal: False
The mirror covers only Theorem 4(a)’s NP-completeness result; it leaves Theorem 4(b)’s skeptical-acceptance result and the paper’s polynomial-time decision results aside.
The strongest mirror I can defend is a population of argumentation profiles. Think of a large public consultation about one claim \(p\), where people fall into a small number of recurring information profiles. A profile specifies the complete argumentation framework \(G_t=(A_t,R_t)\) available to its members, including the node labeled \(p\). People in the same type are indistinguishable for the question being asked; their mass \(\mu_t\) is their fraction of the population. A realistic regime might have millions of people but only dozens of standardized profiles.
My lead anchor is Theorem 4(a), proved in this paper. It says that \(\mathrm{CA}_{\mathrm{GR}^*}\) is NP-complete: given an AF \(G\) and argument \(x\), decide whether some resolution-based grounded extension contains \(x\). Here, \(\mathrm{GR}^*\)-extensions are the inclusion-minimal sets that occur as grounded extensions of full resolutions of \(G\). The paper proves membership in NP using its polynomial-time verifier, Theorem 3. For hardness it reduces from 3-SAT: literal arguments attack the clause arguments in which they occur, each variable’s two literal arguments mutually attack, and every clause argument attacks a target argument \(\varphi\). The target is credulously accepted exactly when the formula is satisfiable.
The continuous question is Mass-Credulous-\(\mathrm{GR}^*\). An instance consists of a finite support \(Q\) of types, positive binary-rational masses \(\mu_t\) summing to \(1\), an AF \(G_t\) for each type with the common claim \(p\) among its arguments, and a rational threshold \(q\in(0,1]\). Each unit of population has one type and can be assigned one of that type’s ordinary \(\mathrm{GR}^*\)-extensions. Let \(z_{t,S}\) be the mass of type \(t\) assigned extension \(S\). Ask whether
\[ \max \sum_{t\in Q}\ \sum_{\substack{S\in E_{\mathrm{GR}^*}(G_t)\\p\in S}} z_{t,S}\ \ge q, \qquad z_{t,S}\ge 0,\quad \sum_{S\in E_{\mathrm{GR}^*}(G_t)} z_{t,S}\le\mu_t. \]
Thus the decision variable is the mass assigned to each extension, and the objective is the largest share of the population that can be placed in a resolution-based grounded extension supporting \(p\). The extensions themselves remain sets of arguments; what becomes continuous is the population assigned to them.
The hardness transfer is direct. With one type of mass \(1\) and threshold \(q=1\), the question is exactly the paper’s credulous-acceptance question. So Theorem 4(a)’s 3-SAT reduction carries over verbatim, and the continuous problem is NP-hard even when \(\tau=1\). It is in NP as well: guess enough types to reach the threshold and one supporting extension for each, then verify those extensions using Theorem 3. I therefore expect Class B: the hard combinatorics live in the argumentation framework, and putting many people in a type does not remove them.
The mirror covers Theorem 4(a), not the paper’s full complexity analysis. It also raises natural follow-up questions: what is the complexity of computing the exact optimum mass; which restrictions on the AFs make the threshold problem tractable or fixed-parameter; and what is the corresponding mass question for skeptical acceptance in Theorem 4(b)?
The weak point is that a type here is an entire argumentation profile, not a repeated argument inside one shared AF. The authors could regard this as a high-multiplicity batch of their acceptance problem, rather than a new semantics for one continuously populated framework. I think the profile scenario is plausible—people can share standardized evidence and attack structures while differing across a modest set of profiles—and it preserves their exact credulous-acceptance question inside each type. But the case is strongest when the intended application really does ask for the population share across such profiles.
Theorem 4(a) is a real computational anchor, so I would not dismiss it because its NP-hardness survives at one type. The problem is what the proposed population adds. For each type \(t\), all its mass can be assigned to one extension containing \(p\) whenever such an extension exists. Its optimum therefore collapses to
\[ \sum_{t:\,p\text{ is credulously accepted in }G_t}\mu_t. \]
There is no competition or coupling between types, and no population-level \(\mathrm{GR}^*\) outcome. The extension choices in the paper are alternative outcomes for one framework; treating them as choices made by different people requires an extra behavioral assumption. The proposed LP turns out to be a weighted tally of independent acceptance tests.
A stronger version would ask directly what fraction of people’s frameworks make \(p\) credulously accepted. That is a coherent statistic for a population with recurring argumentation profiles. But it places a distribution over input instances; it does not make the population part of the argumentation semantics. With an explicit support, the calculation is just a weighted sum of per-framework answers. Its usefulness would come from that particular survey or application, not from a continuous computational question about \(\mathrm{GR}^*\).
Trying to construct one shared framework from the population does not resolve this. Counting people who endorse an attack, or applying a mass threshold to attacks, would require a rule for turning those counts into a graph or weighted semantics. Replicating one framework across a population leaves its acceptance question unchanged; duplicating arguments changes the framework’s attack structure, since arguments are claims, not agents. Those routes introduce a different model whose relationship to the paper’s results would need to be established.
So the negative case is that the anchor has no natural population-level operation to continuize: its population versions either tally independent frameworks or change the semantics. This case is not airtight. A weighted acceptance statistic could be valuable in a concrete application, and the profile scenario makes it plausible. But on the paper alone, that is a weaker claim for the programme than a continuous mirror of the paper’s computational problem.
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.