| paper | d4-conf-ecai-2023-0170 |
| 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}\text{-complete}\), already for \(\tau=1\) with all arguments and attacks certain and only supports uncertain. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a common argument vocabulary \(U\), a finite support of \(s\)-iBAF types \(IF_t\) over \(U\), binary-rational masses \(\mu_t\) summing to \(1\), a set \(S\) of arguments certain in every type, and a rational threshold \(q\), decide whether \(W \ge q\), where \(W=\sum_{t:\,\exists\text{ completion of }IF_t\text{ in which }S\text{ is an }s\text{-ad extension}}\mu_t\).
Each type \(t\) is a juror assessment template \(IF_t\) with mass \(\mu_t\). Let \(z_t=1\) exactly when some completion of \(IF_t\) makes \(S\) an \(s\)-ad extension, and \(z_t=0\) otherwise; the population quantity is \(W=\sum_t\mu_t z_t\).
The paper motivates uncertain relations by merging jurors’ views into one iBAF, whereas this mirror gives each juror a separate iBAF and measures whose view makes \(S\) possible in some completion. That prevalence is not the same as collective acceptance in one shared dispute.
fatal: False
The mirror covers the possible \(s\)-ad verification case from Theorem 2. It leaves the theorem’s other semantics and the paper’s remaining verification and acceptance results unaddressed.
The strongest mirror I see is an aggregate version of the possible-admissibility question, using the paper’s jury motivation. Imagine a large public consultation on a common issue: many people reason over the same finite vocabulary of claims, but their assessments of which claims and relations are settled or uncertain fall into a small number of recurring templates. A type is one complete, task-relevant template—an iBAF specifying its certain and uncertain arguments, attacks, and supports. If \(N\) people fall into \(\tau\) such types, with \(\tau \ll N\), the society is the distribution \(\mu\) of their population shares. The paper itself motivates uncertain supports by jurors disagreeing about whether one claim supports another. Here the uncertainty inside each type remains qualitative; \(\mu_t\) means the fraction of people with that assessment template, not the probability that an edge exists.
My lead anchor is Theorem 2, proved in this paper. It states that over \(s\)-iBAFs, possible-perspective extension verification—whether a proposed set \(S\) is an extension in at least one completion—is NP-complete under \(s\)-ad, \(d\)-co, \(s\)-co, \(d\)-gr, and \(s\)-gr. For the lead case, \(s\)-ad means that in some completion, \(S\) is defended and safe under the abstract semantics of supports.
The continuous problem is Mass-IBVER\(_{s\text{-ad}}\). An instance consists of a common argument vocabulary \(U\), a finite support of \(s\)-iBAF types \(IF_t\) over \(U\), binary-rational masses \(\mu_t\geq 0\) summing to \(1\), a proposed set \(S\) present as certain arguments in every type, and a rational threshold \(q\in[0,1]\). For each type, count its mass if there exists a completion of \(IF_t\) in which \(S\) is an \(s\)-ad extension. The task is to compute the counted share
\[
W=\sum_{t:\,S\text{ is an }s\text{-ad extension in some completion of }IF_t}\mu_t,
\]
or decide whether \(W\geq q\). Thus the result being computed is the fraction of the population whose assessment template admits \(S\) as a defensible, safe position under at least one of its possible completions.
The authors could plausibly recognize this as a population-level version of their question: it retains their graph semantics and possible perspective, while asking for the share of a high-multiplicity audience whose views permit the proposed position. It is also a precise hardness mirror. With one type of mass \(1\) and \(q=1\), Mass-IBVER\(_{s\text{-ad}}\) is exactly the \(s\)-ad case of their verification problem, so Theorem 2 transfers NP-hardness directly. I would expect hardness to transfer, since the reduction’s combinatorics live in the argument graph, not in the number of people. This does not claim a tractability gain from continuization; it makes the aggregate question computable as a weighted sum of type-level answers, whose complexity remains to be characterized.
The scope is just Theorem 2’s possible verification hardness under \(s\)-ad. Natural follow-up questions are whether the threshold version is harder than its single-type restriction, whether exact computation of \(W\) has counting complexity, and which restrictions on the argument graphs or uncertain relations make it tractable.
The weak point is that the paper’s iBAF represents uncertainty in an argumentation graph, while my population mass represents how many people share a graph-assessment template. That is an additional aggregation layer, not the paper’s original verification task. The jury motivation makes the layer credible, but the authors might still regard “the share of people whose view admits \(S\)” as a new social-reasoning question rather than their continuous analogue.
Theorem 2 is a real computational anchor, so the case cannot be that the paper has nothing to mirror. The difficulty is that the proposed \(W\) counts people’s separate argumentation frameworks; it does not make a population part of the paper’s verification problem.
For each type \(IF_t\), the proposal first answers the paper’s original question: is \(S\) an \(s\)-ad extension in some completion? It then weights that yes-or-no answer by \(\mu_t\). Putting all mass on one type recovers Theorem 2 exactly, but that is also the limit in which the population disappears. With several types, the new question is how common a particular answer is across a batch of different frameworks. The paper gives no collective semantics in which those frameworks jointly determine whether \(S\) is an extension.
The jury example makes that batch question plausible, but it does not quite bridge the gap. There, differing views about a support relation motivate merging subjective views into one incomplete framework. The proposed mirror instead gives each juror a separate framework, then counts the juror if *some* completion of that framework admits \(S\). That is a measure of whose model leaves \(S\) possible, not a measure of who accepts \(S\) or supports it. It could be useful, but it changes the subject from verification in one uncertain dispute to polling over many people’s uncertain disputes.
A stronger collective version would combine the jurors’ arguments and relations into a shared, mass-weighted framework. But the paper supplies no rule for doing that. Thresholding relation masses could discard correlations that affect supported and supermediated attacks; keeping the full distribution over frameworks brings us back to \(W\), the separate-instance statistic. Choosing an aggregation rule and a mass-based extension semantics could produce a worthwhile project, but those choices would define a new reasoning problem rather than continuize Theorem 2.
One could also ask how much mass must be persuaded or reclassified before \(S\) becomes possible for a given share of the population. That is a coherent intervention question, but it requires a model of what changes a person’s framework and at what cost. The paper’s verification results would then be subroutines for a new campaigning problem, rather than results about a continuous population.
This is a limited negative case, not a decisive one. The authors’ jury motivation gives the proponent a credible route to arguing that the share of jurors for whom \(S\) remains possible is their problem in a population setting. If they accept that interpretation, the mirror survives, and Theorem 2 transfers through the single-type case. My objection is that the paper does not itself establish that collective interpretation; the population layer can be added, but its social meaning and semantics have to come from elsewhere.
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.