| paper | d4-conf-aaai-2024-1378 |
| 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: \(\Sigma_2^{\mathrm P}\)-complete; in particular, \(\mathrm{NP}\)-hard. · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 50
statement extracted from the paper’s text layer
Given \(\tau\) supported types \(t=(D_t,a_t)\), where \(D_t\) is a finite ABA+ framework and \(a_t\) an assumption, rational masses \(\mu_t\ge 0\) summing to \(1\), and a rational threshold \(q\), decide whether \(\sum_{t=1}^{\tau}\mu_t\,\mathbf{1}[\exists E\in\Theta\text{-com}(D_t):a_t\in E]\ge q\).
A type is a recurring case specified by its complete ABA+ query \((D_t,a_t)\); its mass \(\mu_t\) is the population share of cases of that type. Each type has an integral yes-or-no credulous acceptance answer, and the task is to decide whether the exact weighted prevalence reaches \(q\); there is no choice among extensions or other optimization variable.
The masses aggregate separate query instances and do not affect attacks, defenses, or extensions, so the problem is workload prevalence rather than a population-level ABA+ semantics question.
fatal: False
The mirror covers Theorem 50’s credulous acceptance result under Θ-complete semantics; it leaves the other complexity results, semantic correspondence results, and HYPAF translation untouched.
My lead is a high-multiplicity version of the paper’s credulous acceptance under \(\Theta\)-complete semantics. Consider a large service running ABA+ reasoning on recurring case templates—for example, policy checks handled by many independent decision units. A unit’s type is the complete query it processes: an ABA+ framework \(D_t\), including its rules and preference ordering, and a target assumption \(a_t\). Units of the same type are indistinguishable for this task. If the service handles \(N\) units but only \(\tau\) distinct templates, with \(N\) much larger than \(\tau\), represent the society by rational masses \(\mu_t\), the fraction of units of each type.
Here is the resulting problem, \(\Theta\)-Credulous Prevalence. Given the supported types \(t\), their masses \(\mu_t\), and a rational threshold \(q\), let
\[
\chi_t =
\begin{cases}
1 & \text{if some } E\in\Theta\text{-com}(D_t) \text{ contains } a_t,\\
0 & \text{otherwise.}
\end{cases}
\]
Decide whether
\[
W_\Theta(\mu)=\sum_t \mu_t\chi_t\ge q.
\]
The type-level answer remains the paper’s yes-or-no credulous acceptance question; the population-level output is the exact share of units whose target is credulously accepted. There is no action to optimize in the anchor, so this mirror does not invent one: \(\chi_t\) is determined by the semantics, and \(W_\Theta\) is the quantity being reported. Each unit has an integral answer; only the aggregate share is fractional.
The anchor is Theorem 50, proved in this paper: the table states that credulous acceptance under \(\Theta\)-complete semantics is \(\Sigma_2^P\)-complete. In full, given an ABA+ framework \(D\) and an assumption \(a\), the problem is to decide whether there exists a \(\Theta\)-complete extension of \(D\) containing \(a\). The paper introduces these \(\Theta\)-semantics to guarantee an extension, and its complexity table gives this acceptance problem the stated completeness result.
This is a credible high-multiplicity regime when a service processes many units drawn from a comparatively small library of complete case templates. Mass means share of workload or cases, not a fractional assumption or a fractional extension. The mirror covers this one reasoning result; it does not continuize the paper’s HYPAF translation, its abstract attack structures, or all of its complexity table.
I expect hardness to transfer. Set \(\tau=1\), \(\mu_t=1\), and \(q=1\). Then the prevalence question is exactly the anchored credulous-acceptance problem. Thus continuous mass does not dissolve this hardness in this mirror. With multiple supported types, aggregation may affect the exact complexity; further questions include its classification as a function of \(\tau\), and whether a shared framework across types yields useful algorithms. But the one-type reduction already gives the continuous problem the paper’s \(\Sigma_2^P\)-hardness.
The weakest point is that the paper studies reasoning about one framework, not a population of reasoning services. This scenario makes a workload of their queries into a population statistic, so the authors might view it as a useful high-multiplicity batch problem rather than a central ABA+ problem. The case survives only if that batch question is accepted as their credulous-reasoning problem at population scale. It should not be presented as a new semantics or as a route to easier computation.
The anchor is real: Theorem 50 gives \(\Sigma_2^P\)-completeness for credulous acceptance under \(\Theta\)-complete semantics. And the proposed workload statistic is well-defined. I would not attack it on the ground that its answer stays hard, or that the arithmetic over masses is simple.
The difficulty is what the masses describe. If every unit uses the same ABA\(^+\) framework and asks the same question, the units are copies of one query and the prevalence is just its yes-or-no answer. If they ask different questions about one shared framework, prevalence is a weighted summary of answers for different assumptions. If their frameworks differ, each type is effectively a separate reasoning instance. In the last two cases the population does not enter the attacks, defenses, or extensions: solve each query, then weight the answers. That can be useful batch reporting, but it gives the paper’s semantics no population-level problem to solve.
The strongest version of the service scenario is credible: repeated case templates could make a large workload with small support. But its computational substance remains evaluating Theorem 50 on those templates and aggregating the results. The continuous data affect the reported share, not which extensions exist or what is accepted. This is a plausible application of ABA\(^+\) reasoning; the case that it is a worthwhile continuization of this paper is weaker.
A closer population model might give stakeholder types distributions over assumptions, then ask for a \(\Theta\)-complete extension that represents the greatest mass of stakeholders. That makes mass affect an optimization objective, but adds a choice among extensions based on social support. In the paper, extensions are possible accepted sets, not outcomes selected to maximize representation; it supplies no stakeholder preferences or rule for measuring satisfaction. Treating assumptions as population types has the same gap: assumptions are jointly interacting propositions, not agents, and the paper’s semantics contains no mass-sensitive version of their acceptance. This could motivate a separate weighted argumentation problem, but it is not supplied by the complexity result itself.
So my negative case is that a meaningful mirror needs a new collective decision layer. The stated anchor instead measures a workload of reasoning queries. That is a defensible distinction, not a proof that no useful population-based argumentation problem can be devised. The batch scenario is the weak point in the negative case: it is plausible, and a reader could reasonably judge that its aggregate is useful enough to count.
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.