| paper | d4-conf-ijcai-2011-0152 |
| 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 under polynomial-time Turing reductions, already for \(\tau=1\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 7
statement extracted from the paper’s text layer
Given a common argument set \(X\) and an explicitly listed support \((F_i,\mu_i)_{i=1}^{\tau}\) of frameworks with \(\sum_i\mu_i=1\), output the exact rational vector \(p\) where \(p(a)=\sum_{i=1}^{\tau}\mu_i\,\mathbf{1}[a\in I_{\mathrm{sst}}(F_i)]\) for every \(a\in X\).
A population of independent decision units, each assigned a complete framework type \(F_i\) and mass \(\mu_i\). Each unit’s accepted arguments remain discrete; the output records their population shares.
The profile aggregates answers to separate frameworks, so its population-level meaning is prevalence across independent reasoning units rather than acceptance in one shared debate.
fatal: False
The mirror covers Theorem 7’s semi-stable construction result and also supports the stage ideal-acceptance result; it leaves the paper’s other complexity bounds and comparisons among semantics at the single-framework level.
The strongest faithful mirror is a population of independent argumentation systems. Imagine a large cohort of deployed decision units, each handling one case under the paper’s ideal semantics. They share a common set of argument labels \(X\), but use one of \(\tau\) attack structures \(F_i=(X,A_i)\). An agent’s complete type is its framework \(F_i\); its mass \(\mu_i\) is the fraction of the cohort using that type. A realistic regime has many repeated cases and templates, so the number of agents \(N\) is much larger than \(\tau\). Each agent’s acceptance remains discrete; only the population-level totals are fractional.
For the semantics used below, let \(I_\sigma(F)\) denote the unique ideal extension of \(F\) with base semantics \(\sigma\). The paper establishes uniqueness for the relevant base semantics. This mirror keeps the paper’s reasoning problem intact and asks for aggregate results across a distribution of frameworks; it does not make attacks or individual arguments fractional.
Lead: Continuous Semi-Stable Ideal Profile. Given the support \((F_i,\mu_i)_{i=1}^{\tau}\), output, for every \(a\in X\), the mass of agents whose semi-stable ideal extension contains \(a\):
\[
p(a)=\sum_{i=1}^{\tau}\mu_i\,\mathbf{1}\!\left[a\in I_{\mathrm{sst}}(F_i)\right].
\]
The solution is the exact rational vector \(p\). This is a population-level construction problem, with no intervention or optimization variable.
The anchor is Theorem 7, specifically its semi-stable entry in Table 2. The paper proves that constructing the ideal extension with respect to semi-stable semantics, \(CONS^{IE}_{\mathrm{sst}}\), is \(\mathrm{FP}^{\Sigma_2^P}_{\parallel}\)-complete. The theorem is proved here. With \(\tau=1\) and mass \(1\), the profile is just the characteristic vector of the original ideal extension. The continuous version is therefore expected to inherit that hardness; with explicit support, it can also be computed by solving the \(\tau\) framework instances and summing their rational masses. This is a Class B mirror: the difficulty already appears in one framework, so it is not caused by population multiplicity.
A second, narrower mirror uses another entry of Theorem 7. The theorem proves that credulous acceptance for ideal sets with stage as the base semantics, \(CA^{IDL}_{\mathrm{stage}}\), is \(\Pi_2^P\)-complete. That problem asks whether there exists an ideal set containing a specified argument \(a\).
Continuous Stage-Ideal Acceptance Share. Given \((F_i,\mu_i)_{i=1}^{\tau}\), an argument \(a\), and a rational threshold \(r\in[0,1]\), decide whether
\[
\sum_{i=1}^{\tau}\mu_i\,\mathbf{1}\!\left[a\in I_{\mathrm{stage}}(F_i)\right]\ge r.
\]
A yes or no answer is the solution. For one type of mass \(1\) and threshold \(1\), this recovers the paper’s stage ideal-set acceptance question. So the population problem is at least \(\Pi_2^P\)-hard; its exact complexity with many types is a further question, since it combines queries across the support. This is also expected to be Class B, for the same reason.
These are deliberately limited mirrors of the two stated results, not a claim to continuize the paper’s entire complexity landscape. They also generate natural follow-up questions: how the aggregate problems depend on \(\tau\), which graph restrictions make them easier, and how much the acceptance profile can change when a small amount of mass shifts between framework types.
The weak point is that an abstract argumentation framework describes a reasoning instance, not a population of interacting people. A referee might regard this as continuous aggregation of a workload rather than an intrinsic population model of argumentation. The case for accepting it is that a cohort of independent decision units really does have a type distribution, and every unit’s output is computed using exactly the paper’s semantics. I would present it as a credible, bounded population mirror—not as evidence that the paper itself models collective social reasoning.
The paper has genuine computational anchors, so the case against cannot rest on the absence of a result. Theorem 7 gives both the \(\mathrm{FP}^{\Sigma_2^P}_{\parallel}\)-completeness of constructing a semi-stable ideal extension and the \(\Pi_2^P\)-completeness of stage ideal-set acceptance. The question is whether the proposed population problems are good mirrors of those results.
The semi-stable profile is the stronger anchor. Its most charitable interpretation is a large cohort of independent decision units, each applying ideal semantics to a framework type. That is a coherent high-multiplicity workload: with support \((F_i,\mu_i)\), the profile \(p(a)\) is well-defined, and the finite cohort version differs only by replacing masses with counts. But the cohort’s members do not form one argumentation society. Each framework is a whole debate; its arguments and attacks jointly determine its ideal extension. If frameworks are pooled to represent a shared debate, the profile of separate answers need not describe the result. For example, half the cohort could use \(a\to b\) and half \(b\to a\), giving separate ideal extensions \(\{a\}\) and \(\{b\}\). The profile assigns each argument mass \(1/2\). Pooling those attacks produces mutual attack, whose preferred extensions are \(\{a\}\) and \(\{b\}\), but whose ideal extension is empty. The profile answers “in what fraction of independent frameworks is \(a\) accepted?”, not “what does the society accept?”
That distinction is not a claim that inherited hardness is uninteresting: the programme explicitly values Class B results. It is that the continuous mass in this proposal only weights answers to separately solved instances. With explicit support, one computes the \(\tau\) ideal extensions and sums their indicators. The theorem’s hardness already appears at \(\tau=1\); varying the masses does not create a population-level computational object. A repeated-case cohort may be plausible, but then the mirror is about aggregating a workload’s outputs rather than the paper’s collective reasoning problem.
The stage acceptance-share anchor has the same problem. At support size one and threshold \(1\), it recovers the paper’s acceptance question exactly. For multiple types, it is a weighted tally of the corresponding answers. That can be a useful statistic about a cohort, but it adds no interaction among types or new semantic challenge. A stronger proposal might allow interventions to move mass between framework types until an argument reaches a target support share. Yet a cost for editing attacks measures changes to a debate’s representation, not a standard change in an individual’s preferences or vote. It could become a sensible new model if authors supplied a convincing account of such interventions; it is not supplied by these results.
Making participants contribute arguments to one shared framework does not rescue the anchors directly. Arguments and attacks are interdependent parts of the object being reasoned over, not interchangeable agents whose masses can simply be substituted. A continuous attack-density model might be worth studying, but it needs new semantics for how fractional relations affect defense and maximality. The paper’s theorems do not identify that model or its computational questions.
So the strongest negative case is that both proposed mirrors obtain a population only by treating independent frameworks as agent types, and their continuous questions then tally independent outputs. That is a defensible cohort model, but a weak fit for a programme about the computational consequences of making society continuous. The case is not airtight: if the programme accepts population statistics over repeated reasoning systems as a worthwhile target, these anchors survive. The paper alone does not rule out that broader direction.
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.