| paper | d4-conf-ijcai-2017-0327 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: Finding even one maximizer is \(\mathrm{NP}\)-hard. Polynomial-delay enumeration, including preprocessing, would imply \(\mathrm P=\mathrm{NP}\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
For a fixed argument set \(Arg\), let each type be an observation mask \(S\subseteq Arg\) together with a positive or negative status for every argument in \(S\). Given a rational distribution \(\mu\) over these types, let \(q_{A,\epsilon}(\sigma)\) be the probability of the observed statuses under the paper’s model for candidate attack relation \(A\) and semantics \(\epsilon\), conditional on the mask. Find every \(A\) maximizing \(\max_{\epsilon\in\{g,p,s,c\}}\sum_{\sigma}\mu_{\sigma}\log q_{A,\epsilon}(\sigma)\), the limiting per-capita log likelihood.
A fixed set of arguments and a rational mass distribution over participants’ observed-status patterns; the unknown is the attack relation \(A\), and the objective is the paper’s Bayesian status likelihood per capita, optimized over semantics. Participants with the same observed pattern form one type.
The support-based decoder also works on a finite sample once the required extension records appear, and Theorem 2 does not establish that the true relation maximizes the proposed smoothed rate objective.
fatal: False
The mirror covers the paper’s inference of attack relations from observed acceptability statuses, with Theorem 2 as its exact-recovery anchor; it leaves aside the paper’s other estimator properties and its illustrative forum analysis.
There is no named complexity-class result in this paper: it proves no P, NP-hardness, FPT, or similar classification. The strongest named computational anchor is Theorem 2, proved in this paper. It says that for any symmetric, irreflexive true attack relation \(att^*\), and any \(\epsilon\in\{c,p,s\}\) (complete, preferred, or stable semantics; not grounded), the Bayesian MAP estimate over attack relations is exactly \(att^*\) when the observations include the canonical acceptability-status record for every \(\epsilon\)-extension of \(\langle Arg,att^*\rangle\). The candidate relations in that MAP search are not restricted to be symmetric or irreflexive.
My lead mirror is Continuous Attack Estimation. Fix \(k\) arguments and let a type \(\sigma\in\{+,-,?\}^k\) record one forum participant’s positive, negative, or missing status for each argument. The instance is a rational distribution \(\mu\) over these records, with support size \(\tau\). For a candidate attack relation \(A\) and semantics \(\epsilon\), let \(q_{A,\epsilon}(\sigma)\) be the paper’s probability of that record: average over the extensions of \(\langle Arg,A\rangle\), using its status estimator. For example, with the paper’s Laplace settings, a reported status matching an extension gets probability \(2/3\), and a mismatch gets \(1/3\).
The decision variable is \(A\). The objective is the limiting per-capita log likelihood
\[
F_\mu(A)=\max_{\epsilon\in\{g,p,s,c\}}\sum_{\sigma}\mu_\sigma\log q_{A,\epsilon}(\sigma).
\]
The problem is to return every attack relation maximizing \(F_\mu\). This is the high-multiplicity limit of the paper’s Bayesian inference: with \(N\) participants and proportions \(\mu\), the likelihood has factors \(q_{A,\epsilon}(\sigma)^{N\mu_\sigma}\), and its leading rate as \(N\) grows is \(F_\mu(A)\). A concrete regime is a large forum discussing a fixed set of arguments. Millions of participants may reduce to a much smaller set of distinct vote patterns, so the data are masses over types rather than individually targeted users.
The Theorem 2 regime gives this mirror a credible foothold: \(\mu\) has positive mass on the canonical records for every extension of an unknown symmetric, irreflexive relation under complete, preferred, or stable semantics. In that regime, the extension records themselves reveal the relation: two distinct arguments are connected exactly when they never occur together in an extension. For an undirected loop-free attack graph, every non-edge pair extends to a maximal independent set, which is stable and also preferred and complete. Thus support decoding takes \(O(k^2\tau)\) time. I expect this promised slice to be tractable, provided its recovered relation is also the maximizer of the limiting Bayesian objective. Establishing that last step is the continuous counterpart of Theorem 2; the paper does not prove it.
This scope covers attack-relation estimation and Theorem 2’s exact-recovery conditions. It does not cover argument extraction from text or the paper’s empirical question of whether estimated attacks persuade forum participants. The natural next questions are whether the rate-MAP result survives arbitrary positive masses on the extension records, how the unrestricted noisy-data problem behaves, and whether it admits algorithms parameterized by \(k\) or \(\tau\). For the unrestricted problem, I would tentatively expect hardness to persist when it is driven by the number of arguments: the candidate graph carries that combinatorics, and replacing repeated individuals with their masses does not remove it. The paper supplies no hardness result to establish this, however.
The soft spot is the passage from Theorem 2’s finite-sample posterior to the limiting rate objective. The theorem’s priors and smoothed likelihood operate at finite scale; the population-rate objective changes their relative influence. So Theorem 2 motivates the mirror and identifies a meaningful regime, but it does not settle the continuous question. The mirror remains recognizable as the authors’ attack-estimation problem because it keeps the same observations, latent attack relation, semantics, and inference objective at population scale.
The strongest case against this mirror is that it turns a statistical structure-learning problem into a “continuous population” problem without creating a new population-scale computation for the programme to study.
The paper’s Theorem 2 is a real exact-recovery result, but it says nothing about an algorithm’s running time or a complexity classification. Its assumptions are unusually sharp: unsmoothed status likelihoods, and observations covering every extension of the true symmetric, irreflexive attack relation. The proponent’s proposed rate-MAP problem changes that setup. With smoothing, the masses affect the objective and Theorem 2 no longer establishes recovery. Without smoothing, the masses matter only through which records have positive mass.
The proposed support decoder makes the gap clear. Under its promise, the attack graph can be reconstructed from which pairs of arguments co-occur in extension records. The same decoder works on an ordinary finite sample once each required record has appeared. The mass values add nothing to that recovery result. And the decoder does not establish that the graph maximizes the proponent’s smoothed rate likelihood; as they acknowledge, that step remains open.
For the broader rate-MAP formulation, let \(D\) be a common denominator for the rational masses and set \(n_\sigma=D\mu_\sigma\). For a fixed graph \(A\) and semantics \(\epsilon\),
\[ D\sum_\sigma \mu_\sigma\log q_{A,\epsilon}(\sigma) =\sum_\sigma n_\sigma\log q_{A,\epsilon}(\sigma). \]
So the rate objective is the finite likelihood objective on a replicated dataset, with the fixed prior washed out in the limit. The paper already assumes independent observations, and its likelihood uses them through their frequencies. Population size therefore does not create the large optimization structure that continuization often makes tractable; the remaining search is over attack graphs and their semantics. Studying that search may be worthwhile, but it is a graph-inference question whose computational content does not depend on a continuous population.
The online-forum example is a plausible high-multiplicity regime: many participants can share the same status pattern, and named identities do not matter to the model. I would not argue that multiplicity is impossible here. The difficulty is fit with ChoCo’s stated target. These participants supply observations used to infer a latent attack relation; the paper studies no collective choice rule, winner, or intervention on the population. A continuous distribution of their responses is natural statistical language, but it does not bring this paper’s central task into the programme’s population-based computational questions.
That leaves a substantial weakness in the negative case. If ChoCo chooses to include computational inference from distributions of opinion types, the weighted likelihood problem is a sensible question the authors would recognize. My case is strongest against calling it a worthwhile *continuous social-choice mirror*: Theorem 2’s recovery content is already support-based on finite data, and the broader continuous objective is the standard frequency-weighted limit of the paper’s existing inference model.
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.