| paper | d4-conf-ijcai-2017-0120 |
| 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: The unary-threshold problem is \(\mathrm{NP}\)-complete, already for \(k=3\). Exact enumeration has total time polynomial in \(m,\tau,L,N\) if and only if \(\mathrm{P}=\mathrm{NP}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a finite bipartite attack graph \(G=(T_0\dot\cup T_1,R)\) and positive rational masses \(\mu_t\) summing to \(1\), enumerate all vectors \(x\in\prod_{t\in T}[0,\mu_t]\) such that for each \((t,u)\in R\), \(x_t>0\) and \(x_u>0\) do not both hold, and every type \(u\) with \(x_u<\mu_u\) is attacked by some type \(t\) with \(x_t>0\).
Types are standardized argument templates, \(\mu_t\) is their share among repeated submissions, and \(x_t\) is accepted mass. An attack applies across all copies of its endpoint types; stable semantics requires conflict-freeness and attack coverage of every unaccepted copy, forcing \(x_t\in\{0,\mu_t\}\).
The remaining concern is whether repeated argument submissions qualify as a population of agents in ChoCo’s sense; the proposed scenario makes this plausible, but does not model submitter identities.
fatal: False
The mirror covers only Theorem 3’s stable case on bipartite AFs; it leaves the theorem’s complete and stage2 cases and the paper’s other semantics and structural restrictions aside.
The strongest honest mirror I see is narrow: enumerate stable extensions in a high multiplicity population of repeated argument instances. It does not mirror the paper’s whole classification.
Imagine a large deliberation platform that sees many instances of standardized argument templates. A type is a complete argument template, including its attack relations; its mass is the fraction of submissions of that type. There may be \(N\) submissions but only \(\tau\) templates, with \(N\gg\tau\). In the bipartite regime, templates fall into two sides, and attacks run only across sides. Assume an attack between two types applies to every occurrence of the first type and every occurrence of the second. That is a specific, plausible regime for standardized arguments, not a claim about all argumentation frameworks.
Call the resulting problem Bipartite Stable-Extension Enumeration\(_\infty\). Its input is a finite type set \(T=T_0\dot\cup T_1\), a directed attack relation \(R\subseteq (T_0\times T_1)\cup(T_1\times T_0)\), and positive binary rational masses \(\mu_t\) with \(\sum_{t\in T}\mu_t=1\). A solution is an accepted-mass vector \(x\in\prod_{t\in T}[0,\mu_t]\) such that:
The task is to enumerate all such vectors. These are the continuous stable positions: accepted arguments form a conflict-free set and attack everything outside it. In this bipartite model, the conditions force \(x_t\in\{0,\mu_t\}\) for every \(t\). If a type were only partly accepted, its unaccepted mass would need an accepted attacker, but that attacker would also attack the accepted mass of the same type, violating conflict-freeness. Thus the output is finite and has a direct interpretation as extension mass by type.
My anchor is Theorem 3, proved in this paper: for \(\sigma\in\{\mathrm{stable},\mathrm{comp},\mathrm{stage2}\}\), enumerating \(\sigma\)-extensions of bipartite AFs is not in \(\mathrm{OutputP}\) unless \(\mathrm{P}=\mathrm{NP}\). I rely on its stable case: enumerating all stable extensions of a bipartite AF is not output-polynomial unless \(\mathrm{P}=\mathrm{NP}\). The paper proves this using the correspondence between stable extensions and graph kernels, together with the cited NP-hardness of deciding whether a bipartite graph has more than two kernels from Dimopoulos, Magirou, and Papadimitriou (1997).
The continuous problem has the same hardness. Given any bipartite AF \(F=(T,R)\), assign \(\mu_t=1/|T|\) to each type. Its stable extensions \(S\) correspond one-to-one with output vectors \(x_t=\mu_t\) for \(t\in S\) and \(x_t=0\) otherwise. The correspondence persists if each type is replicated by an arbitrarily large number of identical argument occurrences with the same complete cross-type attack pattern. The reduction therefore carries the paper’s hardness into a high multiplicity regime; it does not depend on the total number of copies. I expect this mirror to be Class B: hardness transfers, because the combinatorics live in the attack graph on the \(\tau\) types. Its scope is specifically Theorem 3’s stable, bipartite result, not the other semantics or structural restrictions.
The weakest point is that mass mostly labels the output: stable semantics makes each type all-or-nothing, so changing \(\mu\) does not change which type supports are stable. Also, all-to-all attacks between repeated types are a strong modeling assumption. But adding fractional acceptance thresholds just to make mass affect feasibility would change Dung’s stable semantics. For this narrow regime, the type-level mass vector is a faithful aggregate of the authors’ underlying problem. Natural follow-up questions are whether the same quotient is faithful for complete or stage2 semantics, and whether parameters such as \(\tau\) or the attack graph’s structure yield useful algorithms despite the output-polynomial hardness.
Theorem 3 is a genuine enumeration complexity result, so the “no computational result to mirror” objection does not apply. The stable, bipartite case is also the strongest anchor: it has a clean kernel correspondence and a well-motivated repeated-template story. My objection is that this story does not give the theorem a meaningful population dimension.
In an abstract argumentation framework, vertices are arguments and edges are attacks; they are not agents with preferences or other attributes whose prevalence affects the problem. If many occurrences of one argument template are made into a single type, with attacks uniform across types, stable semantics forces each type to be accepted wholly or rejected wholly. A partly accepted type would have an unaccepted remainder that must be attacked; that same type-level attacker would then attack the accepted portion, violating conflict-freeness. Thus \(x_t\in\{0,\mu_t\}\), and stable extensions are just kernels of the finite type graph. The masses record how many copies were supplied, but do not affect feasibility or the extensions being enumerated.
The forum example is the best rescue, and it remains plausible as an application scenario. But it has to choose what its population counts. If it counts repeated copies of the same argument, those copies are redundant under the proposed all-to-all attack model: one accepted copy already attacks the opposing type, and adding more changes nothing. If the population counts speakers, the enumerated objects are still sets of arguments, while a speaker may contribute several arguments and the relevant attack links can depend on which speakers produced them. Aggregating speakers into types then loses the relations that define the AF. Making attack success depend on endorsement mass could restore a role for mass, but that adds a quorum or weighted-attack semantics; population scaling does not require that change, and it is a different problem from Theorem 3’s stable-extension enumeration.
The discrete lower bound also does not establish a useful high-multiplicity regime: the hard bipartite graph can have a distinct type for every vertex, and replicating each vertex only pads that graph while leaving its kernel problem intact. That observation alone would not disqualify a mirror. The more basic concern is that the proposed continuous input is a weighted encoding of argument duplicates, with no population-dependent quantity for the computational problem to act on.
So I would not count this as a worthwhile continuous mirror for the programme. This is still the weakest part of the negative case: argumentation systems can contain repeated, standardized arguments, and a high-multiplicity quotient of stable extensions is mathematically well-defined. A reader who regards repeated argument occurrences as a genuine population may reasonably keep the anchor.
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.