| paper | d4-conf-aaai-2022-1236 |
| 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: Exact computation is \(\mathrm{NP}\)-hard under polynomial-time Turing reductions for both \(C=\mathrm{ODDFREE}\) and \(C=\mathrm{EVENFREE}\text{-}4\), already for \(\tau=1\) and also for \(\tau=2\) with equal masses. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 4
statement extracted from the paper’s text layer
Fix \(C \in \{\text{ODDFREE},\text{EVENFREE-4}\}\). Given a finite support of types \((F_i,a_i)\), each with \(\operatorname{btw}_C(F_i)=0\), and positive binary-rational masses \(\mu_i\) summing to \(1\), compute exactly \(Q=\sum_i \mu_i\,\mathbf{1}[a_i\text{ belongs to every preferred extension of }F_i]\).
Each type is a deliberation panel with argumentation framework \(F_i\) and queried claim \(a_i\); \(\mu_i\) is its population mass, and the local outcome is \(z_i=1\) exactly when \(a_i\) is skeptically accepted under preferred semantics. The task is to output the exact rational mass \(Q=\sum_i\mu_i z_i\).
The paper studies individual AFs, so prevalence across panels is an aggregate application rather than an internal AF task; the panel scenario makes that extension plausible, but the paper itself does not establish that authors would treat it as part of their problem.
fatal: False
The mirror covers the skeptical preferred-acceptance hardness of Proposition 4 and the reasoning hardness of Proposition 3; it leaves the backdoor-finding and FPT results, system design, and benchmark comparisons aside.
The strongest mirror I believe in is a population of deliberation panels. Each panel uses an argumentation framework to assess a policy claim. A panel’s type is the complete pair \((F,a)\): its AF \(F=(A,R)\) and the queried argument \(a\). Fix the semantics and reasoning task for the whole population. Panels with the same pair are indistinguishable for that task. If many thousands of panels use a relatively small library of recurring argument structures, the population size \(N\) can be much larger than the number \(\tau\) of distinct types.
Give each supported type \(i\) a binary-rational mass \(\mu_i>0\), with \(\sum_i\mu_i=1\). For a reasoning predicate \(P\), let \(z_i=1\) if type \(i\) satisfies \(P\), and \(z_i=0\) otherwise. The continuous problem is to compute the exact accepted mass
\[
Q=\sum_{i=1}^{\tau}\mu_i z_i.
\]
Each panel has a discrete outcome; the population share is continuous. There is no optimization objective or intervention here: the question is how much of the population satisfies the paper’s reasoning predicate. The input lists the AF types and their masses, and a solution is the exact rational \(Q\), equivalently the type-by-type outcomes and their weighted sum. The natural parameters are \(m=\max_i |A_i|\), \(\tau\), and the bit length \(L\) of the masses and AF descriptions.
My lead anchor is Proposition 4, proved in the paper using reductions that build on cited work by Dvořák et al. (2014). It states that skeptical acceptance under preferred semantics is \(\Pi_2^P\)-hard even when \(\operatorname{btw}_C(F)=0\), for \(C\in\{\text{ODDFREE},\text{EVENFREE-4}\}\). The paper notes that the cited reduction establishes hardness for ODDFREE with backdoor size one, adapts the same reduction to EVENFREE-4, and obtains backdoor-treewidth zero. The mirror is Preferred-Skeptical Acceptance Mass: the input is a rational distribution over \((F_i,a_i)\), with every \(F_i\) satisfying the chosen zero-backdoor-treewidth promise; compute
\[
Q=\sum_i \mu_i\,\mathbf{1}\!\left[a_i\in E\text{ for every }E\in\operatorname{pref}(F_i)\right].
\]
Its expected classification is Class B: hardness transfers. With \(\tau=1\) and mass \(1\), computing \(Q\) decides the original skeptical-acceptance question, so the \(\Pi_2^P\)-hardness survives even in a one-type population. The continuous population supplies a sensible aggregate output, but does not remove the hard combinatorics within an AF.
A second anchor is Proposition 3, proved in the paper. It states that reasoning on AFs with \(\operatorname{btw}_C(F)=0\) remains NP/coNP-hard for \(\sigma\in\{\mathrm{adm},\mathrm{com},\mathrm{pref},\mathrm{stb}\}\) and \(C\in\{\mathrm{SYM},\mathrm{BIP}\}\). Its mirror is Zero-Backdoor Acceptance Mass: fix one of the proposition’s semantics, fragments, and standard credulous or skeptical acceptance tasks; give a distribution over \((F_i,a_i)\) satisfying the corresponding promise; compute the mass of types for which the queried argument meets that task. This is again expected to be Class B: the singleton distribution embeds the original reasoning problem and retains its stated NP- or coNP-hardness. Proposition 4 is the stronger anchor for my case because it identifies a specific \(\Pi_2^P\)-hard query under a zero-width promise; Proposition 3 shows that the population interpretation also applies across several other semantics and fragments.
The panel scenario is intended to make the high-multiplicity regime concrete: standardized deliberation workflows can recur across many local consultations, while the attack graph and the queried claim determine everything the reasoning task uses. Labels such as panel identity do not distinguish types if they have no effect on that task. This is a population distribution over reasoning contexts, not a distribution over fractional arguments or extensions. The authors should recognize the local predicate as exactly theirs and the aggregate as a natural population-level question built from it.
This mirror covers the two reasoning hardness results above. It does not claim to mirror the paper’s backdoor-finding results, its FPT results, or its benchmark comparisons. Its weakest point is that it lifts a single-AF query into a weighted batch query. It gives a credible continuous population and an exact mass question, but no new LP, pricing problem, or tractability gain: the hard case is already present at \(\tau=1\). That limits the programme’s algorithmic payoff here, while making this a useful boundary case for the programme’s question of where continuization stops helping.
The difficulty is not that Proposition 3 or 4 would stay hard. Hardness at \(\tau=1\) is a valid Class B outcome if the population problem is worth asking. The difficulty is that the proposed population sits outside the argumentation framework: each “individual” is a whole input AF and query. That makes the proposed mass an aggregate over separate computations, rather than a continuization of the object whose reasoning the paper studies.
For Proposition 4, a stronger version of the panel scenario would ask what fraction of standardized panels accepts the same policy claim skeptically, with each panel’s type specifying its AF and a distinguished argument for that claim. That is coherent and could be useful as an audit statistic. But if type \(i\) has local answer \(z_i\in\{0,1\}\), the result is just \(Q=\sum_i\mu_i z_i\): solve the skeptical-acceptance problem independently for each supported AF, then sum. For a discrete population with \(n_i\) copies of each type, the answer is exactly the same calculation with \(\mu_i=n_i/N\). Repetition changes the weights, not any AF’s feasible extensions or reasoning task. The continuous layer adds rational arithmetic but no coupled computational structure.
Proposition 3 has the same problem across its semantics and fragments. The zero-backdoor-treewidth promise applies separately to each AF; distributing mass over AFs does not combine their backdoors or create a new structural parameter. With few supported types, this is duplicate elimination followed by repeated reasoning. With many types, the computation scales with the explicit support. The singleton reduction shows that the aggregate task inherits hardness; it does not make it a population-level problem the paper’s authors would recognize as theirs. Adding costs for changing panel types or constraints on how many panels can change might create a coupled optimization problem, but those ingredients would define a new intervention task rather than mirror either proposition.
A more direct attempt would treat arguments inside one AF as the population. That runs into a semantic obstacle. Arguments are claims whose attack relationships can be individually decisive: a single attacker can affect whether another claim is defended, regardless of how small a share it would have in a population. A continuum that keeps only almost-everywhere attack structure can discard such decisive exceptions; one that retains them keeps discrete, identity-bearing arguments. Replacing attacks with densities or probabilities may yield an interesting new model, but it changes the reasoning semantics the propositions analyze.
So the negative case is strongest against the proposed mirrors’ computational value and their fit to this paper, not against the possibility of an informative panel statistic. If the authors regard prevalence across a collection of independent AF instances as part of their problem, Proposition 4 in particular could support a legitimate Class B mirror. I do not think the supplied case establishes that recognition: it turns a local reasoning result into a generic weighted batch wrapper, and the direct argument-level continuum does not preserve the paper’s decisive structure.
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.