Answer: Finding even one maximizer is \(\mathrm{NP}\)-hard. Polynomial-delay enumeration, including preprocessing, would imply \(\mathrm P=\mathrm{NP}\).
Theorem 2 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateFor all symmetric and irreflexive attack relations att∗on Arg and acceptability semantics ε ∈{c, p, s} except grounded semantics g, the following relation holds: att∗= arg max att P(att|acc), where acc denotes the sequence of the sets E ∪{¬x|x /∈E}, for all extensions E ∈ε(⟨Arg, att∗⟩).
statement extracted from the paper’s text layer; consult the paper for the exact wording
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.
Let \(Arg\) be an input set of \(m\geq 1\) arguments. Candidate attack relations are all \(A\subseteq Arg\times Arg\), including self-attacks. Write \(\mathcal E_\epsilon(A)\) for the Dung extensions under grounded, preferred, stable, or complete semantics, respectively \(\epsilon\in\{g,p,s,c\}\).
A society is given by its support: a list of \(\tau\) types \(\sigma=(S,z)\), where \(S\subseteq Arg\) and \(z:S\to\{+,-\}\), with positive binary-rational masses \(\mu_\sigma\) summing to \(1\). Here \(\tau\) is the support size, not the number of possible types, and \(L\) is the total input bit length.
Conditional on the mask, choose one extension uniformly; conditional on that extension, statuses are independent. Fix Laplace smoothing: \(w(z_a,E)=2/3\) when \(z_a=+\) exactly when \(a\in E\), and \(w(z_a,E)=1/3\) otherwise. Thus \(q_{A,\epsilon}(S,z)=|\mathcal E_\epsilon(A)|^{-1}\sum_{E\in\mathcal E_\epsilon(A)}\prod_{a\in S}w(z_a,E)\). Semantics with no extensions are unavailable for that candidate; an empty product equals \(1\).
Define \(F(A)=\max_{\epsilon:\mathcal E_\epsilon(A)\neq\varnothing}\sum_\sigma\mu_\sigma\log q_{A,\epsilon}(\sigma)\), using one common semantics for the whole society. Find every maximizing \(A\), retaining all ties and using no prior-based tie-break.
Can all maximizers of \(F\) be enumerated with delay polynomial in \(m,\tau,L\), including preprocessing and termination, or is finding even one maximizer NP-hard?
For finite observations, an identifiability theorem asserts recovery of a symmetric, irreflexive true attack relation from full status vectors of all its extensions under any one of preferred, stable, or complete semantics; it gives no complexity bound. [Source](https://www.ijcai.org/proceedings/2017/0036.pdf)
No result settling this exact distributional likelihood-maximization problem was located.
Finding even one maximizing attack relation is \(\mathrm{NP}\)-hard. More precisely, graph \(3\)-colorability can be decided in polynomial time using one call to a procedure that returns an arbitrary maximizer of \(F\).
Consequently, enumeration with delay polynomial in \(m,\tau,L\), including preprocessing, would imply \(\mathrm P=\mathrm{NP}\).
The reduction below works even when every mask contains at most four arguments and all input masses are positive dyadic rationals. It handles arbitrary ties and the maximization over one common semantics.
We first establish the property that will make the output of the optimization procedure efficiently verifiable.
Lemma. Suppose \(Arg=O\mathbin{\dot\cup}H\), where \(|H|=4\), and an attack relation \(A\) satisfies \(A\cap(O\times O)=\varnothing\). Then all extensions under each of the four semantics can be computed in polynomial time.
Proof. Use complete labellings with labels \(\mathrm{in},\mathrm{out},\mathrm{und}\). Their defining conditions are:
These labellings correspond bijectively to complete extensions. Indeed, for a complete extension \(E\), label \(E\) as \(\mathrm{in}\), the arguments attacked by \(E\) as \(\mathrm{out}\), and the remainder as \(\mathrm{und}\). Completeness gives the first condition, and the definition of the attacked set gives the second. Conversely, these conditions imply that the \(\mathrm{in}\) set is conflict-free and contains exactly the arguments it defends.
Enumerate the \(3^4=81\) assignments of labels to \(H\). Every attacker of an argument in \(O\) belongs to \(H\), so the conditions uniquely determine all labels on \(O\). Check whether the resulting full labelling satisfies the conditions on \(H\).
This enumerates all complete extensions. The other semantics follow from the standard Dung characterizations: preferred extensions are the inclusion-maximal complete extensions, grounded is the least complete extension, and stable extensions correspond to complete labellings without \(\mathrm{und}\) labels. All these operations involve at most \(81\) extensions. \(\square\)
We reduce from \(3\)-colorability of a finite simple graph \(G=(V,D)\), an \(\mathrm{NP}\)-complete problem. This remains \(\mathrm{NP}\)-complete under additional graph restrictions, although those restrictions are unnecessary here. [Garey, Johnson and Stockmeyer](https://doi.org/10.1016/0304-3975(76)90059-1)
Write \(n=|V|\geq1\) and \(e=|D|\). Introduce the observed arguments
\[ O=\{b\}\cup\{x_{v,c}:v\in V,\ c\in\{0,1,2\}\}, \]
and four auxiliary arguments \(H=\{h_0,h_1,h_2,h_3\}\), which appear in no observation. Thus \(m=3n+5\).
Represent a positive status by bit \(1\) and a negative status by bit \(0\). For a latent extension, a bit is \(1\) exactly when its argument belongs to that extension.
There are two kinds of masks. Each has a prescribed latent distribution \(P_M\), uniform on the four listed vectors.
| Mask \(M\), in the displayed coordinate order | Support of \(P_M\) |
|---|---|
| \((b,x_{v,0},x_{v,1},x_{v,2})\), for each \(v\in V\) | \((1,1,1,1),(0,1,0,0),(0,0,1,0),(0,0,0,1)\) |
| \((b,x_{u,c},x_{v,c})\), for each \(\{u,v\}\in D\) and each \(c\in\{0,1,2\}\) | \((1,1,1),(0,1,0),(0,0,1),(0,0,0)\) |
The number of masks is \(K=n+3e\).
Apply the stipulated independent smoothing channel to \(P_M\). Its resulting observed distribution is denoted by \(r_M\). Explicitly, for \(k=|M|\),
\[ r_M(z)=\frac14\sum_{x\in\operatorname{supp}(P_M)} \frac{2^{|\{a\in M:z_a=x_a\}|}}{3^k}. \]
Include every sign vector on every mask as a society type. Hence
\[ \tau=16n+24e. \]
For now, assign auxiliary rational masses
\[ \nu_{M,z}=\frac{r_M(z)}K. \]
These masses are positive and sum to \(1\). Section 5 replaces them by dyadic input masses.
Let \(F_\nu\) denote the objective with masses \(\nu\), and define
\[ U=\frac1K\sum_M\sum_z r_M(z)\log r_M(z). \]
For every candidate \(A\) and every available semantics \(\epsilon\), the quantities \(q_{A,\epsilon}(M,z)\), as \(z\) varies, form a positive probability distribution. Applying \(\log t\leq t-1\) gives
\[ \sum_z r_M(z)\log\frac{q_{A,\epsilon}(M,z)}{r_M(z)} \leq \sum_z\bigl(q_{A,\epsilon}(M,z)-r_M(z)\bigr)=0. \]
Equality holds exactly when \(q_{A,\epsilon}(M,z)=r_M(z)\) for every \(z\). Consequently,
\[ F_\nu(A)\leq U, \]
with equality exactly when one available semantics simultaneously matches every target mask distribution. Call such an attack relation *fitting*.
The smoothing channel is invertible. On one coordinate it maps \((p_1,p_0)\) to
\[ \left(\frac{2p_1+p_0}{3},\frac{p_1+2p_0}{3}\right), \]
and its inverse maps \((q_+,q_-)\) to \((2q_+-q_-,2q_--q_+)\). Independent smoothing on several coordinates is a tensor product of these invertible maps. Therefore, matching \(r_M\) forces the latent extension marginal on \(M\) to equal \(P_M\).
Suppose \(A\) is fitting under \(\epsilon\). Every extension in \(\mathcal E_\epsilon(A)\) has positive sampling probability. Thus the zero-probability latent patterns in the table exclude those patterns from every such extension.
It follows that:
The target marginal also gives \(\Pr(b\in E)=1/4\). Hence extensions of both kinds exist.
An extension omitting \(b\) therefore gives a proper \(3\)-coloring. An extension containing \(b\) contains all of \(O\); since extensions under all four semantics are conflict-free, it also proves
\[ A\cap(O\times O)=\varnothing. \]
We have proved:
Necessary conditions for fitting. A fitting attack relation implies that \(G\) is \(3\)-colorable and has no attacks between observed arguments.
The second condition allows the lemma from Section 1 to be applied to an arbitrary fitting optimizer.
Suppose \(f:V\to\{0,1,2\}\) is a proper coloring. Define four observed sets:
\[ T_0=O, \qquad T_{j+1}=\{x_{v,(f(v)+j)\bmod3}:v\in V\} \quad(j\in\{0,1,2\}). \]
Construct \(A_f\) as follows:
Its stable extensions are exactly
\[ E_i=\{h_i\}\cup T_i \quad(i\in\{0,1,2,3\}). \]
To verify this, a stable extension contains at most one auxiliary argument because they mutually attack. It must contain at least one because observed arguments attack none of them. Once \(h_i\) is selected, conflict-freeness excludes \(O\setminus T_i\), while stability requires every argument in \(T_i\): an omitted such argument would be unattacked by the extension. Conversely, each displayed \(E_i\) is conflict-free and attacks every argument outside it.
Uniform sampling of these four stable extensions gives the prescribed vertex-mask distributions. For an edge and a fixed color, the three cyclically shifted colorings give the patterns \((1,0),(0,1),(0,0)\), each once, because the endpoints have different colors. The remaining extension gives the baseline pattern \((b,x_{u,c},x_{v,c})=(1,1,1)\).
Thus \(A_f\) is fitting and \(F_\nu(A_f)=U\). In particular,
\[ G\text{ is $3$-colorable} \quad\Longleftrightarrow\quad \text{a fitting attack relation exists}. \]
This section ensures that the reduction works even if “binary-rational” requires a finite binary expansion.
First, there is an explicit gap below \(U\) for every non-fitting candidate.
For any available semantics with \(N\) extensions and any mask of size \(k\leq4\),
\[ q_{A,\epsilon}(M,z)=\frac{J}{N3^k} \]
for an integer \(J\), with \(1\leq N\leq2^m\). The target probability has the form \(r_M(z)=R/(4\,3^k)\). Therefore, if these probabilities differ,
\[ |q_{A,\epsilon}(M,z)-r_M(z)| \geq\frac1{4N3^k} \geq\frac1{324\,2^m}. \]
Also, every target probability is at least \(1/81\).
For positive probability vectors \(r,q\) with every \(r_z\geq1/81\), set \(d_z=q_z-r_z\) and
\[ f(t)=\sum_z r_z\log\frac{r_z}{r_z+td_z}. \]
We have \(f(0)=f'(0)=0\), since \(\sum_zd_z=0\). Every denominator is a probability and is at most \(1\), so
\[ f''(t)=\sum_z\frac{r_zd_z^2}{(r_z+td_z)^2} \geq\frac1{81}\sum_zd_z^2. \]
Integrating twice yields
\[ \sum_zr_z\log\frac{r_z}{q_z} =f(1) \geq\frac1{162}\sum_z(q_z-r_z)^2. \]
Consequently, if \(A\) is non-fitting, every available semantics misses at least one target probability, and
\[ F_\nu(A)\leq U-\gamma, \qquad \gamma=\frac1{162K\,324^2\,2^{2m}}. \]
Now order the \(\tau\) types arbitrarily and choose an integer \(B\) satisfying \(2^B>100\tau/\gamma\). Set
\[ \mu_j=2^{-B}\lfloor2^B\nu_j\rfloor \quad(j<\tau), \qquad \mu_\tau=1-\sum_{j<\tau}\mu_j. \]
All these masses are positive: \(\nu_j\geq1/(81K)\), the choice of \(B\) makes \(2^B\nu_j>1\), and \(\mu_\tau\geq\nu_\tau\). They are dyadic and sum to \(1\). Moreover,
\[ \|\mu-\nu\|_1<2\tau\,2^{-B}<\frac{\gamma}{50}. \]
Take natural logarithms, without loss of generality. Since every mask has size at most four, all model probabilities are at least \(1/81\), so \(|\log q|<5\). Uniformly over candidates and available semantics, perturbing the masses changes the objective by at most
\[ \eta=5\|\mu-\nu\|_1<\frac{\gamma}{10}. \]
The same bound holds after maximizing over semantics.
When \(G\) is colorable, the fitting witness has actual objective at least \(U-\eta\). Every non-fitting candidate has actual objective at most \(U-\gamma+\eta\), which is strictly smaller. Therefore:
Every maximizer for the actual dyadic society is fitting whenever \(G\) is colorable.
The encoding is polynomial: \(B=O(m+\log K+\log\tau)\), and the construction has polynomially many types.
Given \(G\), construct the dyadic society and obtain any maximizing attack relation \(A^\star\). No semantics or likelihood value needs to be returned.
Apply this polynomial-time decoder:
These checks use exact rational arithmetic, not comparisons between logarithms.
If \(G\) is colorable, Section 5 guarantees that every maximizing output is fitting. Section 3 guarantees that it passes the first check, and the remaining checks recognize its fitting semantics.
If \(G\) is not colorable, Section 3 proves that no attack relation is fitting. Thus the decoder always answers no.
The decoder can also extract a coloring on a yes-instance: choose any enumerated extension omitting \(b\), and read its unique selected color at each vertex.
This proves the claimed hardness with one optimization call and polynomial postprocessing. It applies to every maximizing output, so retaining ties or choosing a different output order cannot avoid the reduction.
For every input, a maximizer exists: there are finitely many candidate relations, and grounded semantics is always available.
An enumerator with polynomial preprocessing and polynomial delay would therefore return its first maximizer in polynomial time. Composing it with the decoder would decide graph \(3\)-colorability in polynomial time.
Hence the requested polynomial-delay enumeration would imply \(\mathrm P=\mathrm{NP}\). The proof concerns the specified likelihood objective directly; it does not rely on the cited [identifiability theorem](https://www.ijcai.org/proceedings/2017/0036.pdf).
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output establishes hardness of finding an arbitrary maximizer through a polynomial-time reduction with one optimization call and polynomial-time postprocessing. It also establishes that polynomial-delay enumeration, including preprocessing, would imply \(\mathrm P=\mathrm{NP}\).
I found no major or minor mathematical issues. The audit below checks the supplied argument without adding a replacement proof.
The complete-labelling conditions are correct. They handle arguments without attackers, mutual attacks, and self-attacks.
The asserted correspondence with complete extensions is valid: the labelling records membership in the extension, attacks by the extension, and the remaining arguments. Its conditions express conflict-freeness and the requirement that an argument belongs to the extension exactly when the extension defends it.
Under \(A\cap(O\times O)=\varnothing\), every attacker of an observed argument belongs to \(H\). Consequently, assigning labels to \(H\) uniquely determines the labels on \(O\). Checking the conditions on \(H\) then checks the entire labelling. Enumerating the \(81\) assignments therefore enumerates all complete extensions without omissions.
The characterizations used to obtain preferred, grounded, and stable extensions are correct for the finite argumentation frameworks considered here. In particular, preferred extensions are precisely the inclusion-maximal complete extensions, grounded is the least complete extension, and stable extensions correspond to complete labellings without undecided arguments. The underlying extension relationships are consistent with [Dung’s definitions and Theorem 25](https://cse-robotics.engr.tamu.edu/dshell/cs631/papers/dung95acceptability.pdf).
There are at most \(81\) complete extensions, so all subsequent filtering and inclusion comparisons take polynomial time. No symmetry or irreflexivity assumption is needed.
The source problem is appropriate: graph \(3\)-colorability is NP-complete, including on restricted classes of finite simple graphs. The cited [Garey–Johnson–Stockmeyer paper](https://doi.org/10.1016/0304-3975%2876%2990059-1) supports this premise.
The construction has \(m=3n+5\) arguments and \(K=n+3e\) masks. Since \(n\geq1\), division by \(K\) is valid.
Each vertex mask has four distinct latent vectors and \(16\) observed sign vectors. Each edge-color mask has four distinct latent vectors and \(8\) observed sign vectors. Thus the stated support size \(\tau=16n+24e\) is correct. Simplicity of the source graph ensures distinct endpoints and prevents duplicate edge masks.
The formula for \(r_M\) applies precisely the stipulated smoothing channel. All probabilities are positive, each mask distribution sums to one, and the auxiliary masses \(\nu_{M,z}=r_M(z)/K\) sum to one over the society.
For every available semantics, the model probabilities over all sign vectors of a fixed mask form a positive probability distribution.
The application of \(\log t\leq t-1\) is valid because both the target and model probabilities are strictly positive. Its equality condition requires equality at every sign vector.
Since every mask receives positive weight, attaining \(U\) requires matching every mask. Maximizing over the finite set of available semantics preserves this condition: equality requires one common semantics that matches all masks simultaneously.
The proof therefore respects the task’s requirement of a common semantics for the whole society.
The single-coordinate inverse of the smoothing channel is computed correctly. Tensor-product invertibility consequently justifies recovering each latent mask distribution from its observed distribution.
Every sampled extension has positive probability, so a zero latent marginal probability excludes the corresponding pattern from every extension of the fitting semantics.
The three stated consequences follow directly from the displayed supports:
The marginal probability of containing \(b\) is \(1/4\), so both kinds of extension exist. An extension omitting \(b\) supplies a proper coloring.
An extension containing all of \(O\), together with conflict-freeness, rules out every attack in \(O\times O\), including self-attacks. This establishes precisely the structural condition needed by the enumeration lemma.
The description “every other auxiliary argument” excludes auxiliary self-attacks, as required by the subsequent witness analysis.
A stable extension contains at most one auxiliary argument because distinct auxiliary arguments mutually attack. It contains at least one because, without an auxiliary argument, it cannot attack any omitted auxiliary argument.
After selecting \(h_i\), conflict-freeness excludes \(O\setminus T_i\), and stability forces inclusion of \(T_i\). Conversely, every displayed \(E_i\) is conflict-free and attacks every omitted argument. The four displayed sets are therefore exactly the stable extensions.
Their uniform distribution matches every vertex mask. For an edge and a fixed color, the endpoints’ distinct colors ensure that the three cyclic shifts produce each of the three required nonbaseline patterns exactly once. The fourth extension produces the baseline pattern.
Hence the witness attains \(U\). Combined with the necessary conditions, this establishes the stated equivalence between colorability and existence of a fitting relation.
The denominator calculation is correct. With \(N\) extensions and a mask of size \(k\), each model probability has denominator \(N3^k\), while each target probability has denominator \(4\,3^k\). Unequal probabilities therefore differ by at least \(1/(4N3^k)\).
The bounds \(N\leq2^m\) and \(k\leq4\) give the stated separation \(1/(324\,2^m)\).
The lower bound \(r_M(z)\geq1/81\) is valid: each smoothed probability conditional on a latent vector is at least \(3^{-k}\).
In the divergence calculation, the interpolated denominators remain positive and at most one throughout the integration interval. The derivatives, their initial values, and the twice-integrated lower bound are correct.
Applying that bound to one differing probability and retaining its mask weight gives exactly
\(\gamma=1/(162K\,324^2\,2^{2m})\).
A non-fitting candidate fails to match under every available semantics. Thus the bound applies separately to each semantics and survives their maximization.
Rounding down the first \(\tau-1\) masses and assigning the residual to the last mass preserves total mass one.
The chosen precision ensures that every rounded mass remains strictly positive. The last mass is at least its original positive value.
The stated bound on the total rounding error is correct. Every model probability is at least \(1/81\), so the logarithm bound gives the claimed uniform objective perturbation. The same perturbation bound holds after maximizing over semantics.
On a colorable instance, the fitting witness has perturbed objective at least \(U-\eta\), while every non-fitting candidate has objective at most \(U-\gamma+\eta\). Since \(2\eta<\gamma\), every actual maximizer is fitting. This argument correctly handles arbitrary ties.
A precision satisfying the inequality can be chosen with \(B=O(m+\log K+\log\tau)\). Both the rational construction and the dyadic rounding therefore have polynomial bit complexity. The auxiliary non-dyadic masses are used only in the analysis; the submitted society has positive dyadic masses.
Rejecting a returned relation with an attack inside \(O\times O\) is valid: no fitting relation has such an attack.
Otherwise, the lemma permits polynomial-time enumeration of every relevant extension family. Computing mask probabilities and checking equality with \(r_M\) uses exact rational arithmetic with polynomial bit lengths.
On colorable instances, every maximizer is fitting and passes the decoder. On noncolorable instances, no relation is fitting, so every returned maximizer is rejected. The decoder consequently works for every possible optimization output.
The established hardness is explicitly a polynomial-time reduction with one call to a search procedure returning a maximizer. The output states this scope correctly; it does not claim a decision threshold reduction or membership in NP.
A maximizer always exists because the candidate set is finite and grounded semantics is always available. Thus an enumerator with polynomial preprocessing and delay must return its first maximizer in polynomial time.
Composing that first output with the decoder decides graph \(3\)-colorability in polynomial time. Termination guarantees are unnecessary for this implication, so including them in the requested enumeration guarantee creates no gap.
The construction also covers edgeless graphs, isolated vertices, and \(n=1\). Unavailable stable semantics in arbitrary candidates are handled by the availability restriction. The proof does not rely on the identifiability theorem.
Repair feedback: none required. The supplied argument resolves the hardness alternative for the specified objective, including dyadic encoding, a common semantics, and arbitrary maximizing ties.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.