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}\).
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateLet σ ∈{stable, comp, stage2}. Then EnumExt(Cbip, σ) ̸∈OutputP holds unless P = NP.
statement extracted from the paper’s text layer; consult the paper for the exact wording
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\).
A society is given by its support: a list of \(\tau\) types with positive binary-rational masses \(\mu_t\), with \(\sum_{t\in T}\mu_t=1\). Here \(\tau=|T|\) is the support size, not the number of possible types.
The input also contains a directed bipartite attack graph \(G=(T_0\dot\cup T_1,R)\), where \(T=T_0\dot\cup T_1\) and \(R\subseteq(T_0\times T_1)\cup(T_1\times T_0)\); opposite attacks are allowed.
A feasible vector is \(x\in\prod_{t\in T}[0,\mu_t]\) with real coordinates satisfying \(\forall(t,u)\in R,\ \neg(x_t>0\land x_u>0)\) and \(\forall u\in T,\ x_u<\mu_u\Rightarrow\exists t\in T:\ (t,u)\in R\land x_t>0\).
The enumeration problem asks for all feasible vectors. Let \(N\) denote their number, \(m=|R|\), and \(L\) the total binary input length; the associated threshold problem asks whether \(N\ge k\), for a positive integer \(k\) supplied in unary.
Does exact enumeration admit total time polynomial in \(m,\tau,L,N\), or is the associated unary-threshold problem NP-hard rather than solvable in time polynomial in \(m,\tau,L,k\)?
For finite directed bipartite argumentation frameworks, enumerating stable extensions is not output-polynomial unless \(\mathrm{P}=\mathrm{NP}\). [Kröll, Pichler and Woltran](https://www.ijcai.org/Proceedings/2017/0159.pdf)
No result settling exactly the mass-vector problem above was located in the literature search.
The unary-threshold problem is \(\mathrm{NP}\)-complete, already for the fixed threshold \(k=3\). Consequently, exact enumeration has total time polynomial in \(m,\tau,L,N\) if and only if \(\mathrm{P}=\mathrm{NP}\).
The key is that the feasibility conditions force every coordinate to be either zero or its full mass.
Define a stable extension of \(G=(T,R)\) to be a set \(S\subseteq T\) satisfying:
Lemma. Every feasible vector satisfies \(x_u\in\{0,\mu_u\}\) for every \(u\in T\).
Proof. Suppose that \(0<x_u<\mu_u\). The second feasibility condition gives some \(t\) with \((t,u)\in R\) and \(x_t>0\). Together with \(x_u>0\), this contradicts the first feasibility condition. Thus no coordinate can lie strictly between its endpoints. \(\square\)
For a feasible vector, let \(S(x)=\{u\in T:x_u>0\}\). The first feasibility condition makes \(S(x)\) conflict-free. If \(u\notin S(x)\), then \(x_u=0<\mu_u\), because every mass is positive. The second condition therefore supplies an incoming attack from \(S(x)\). Hence \(S(x)\) is stable.
Conversely, for a stable extension \(S\), define \(x^S_u=\mu_u\) when \(u\in S\), and \(x^S_u=0\) otherwise. Conflict-freeness verifies the first feasibility condition. Whenever \(x^S_u<\mu_u\), we have \(u\notin S\), and domination verifies the second condition.
The lemma shows that these maps are inverses. Consequently,
\(N=|\{S\subseteq T:S\text{ is a stable extension of }G\}|\leq 2^\tau.\)
In particular, the numerical values of the positive masses do not affect the count.
We use the following known hardness result:
Given a finite directed bipartite graph, deciding whether it has more than two stable extensions is \(\mathrm{NP}\)-complete, even when the graph is strongly connected.
This is the kernel-counting result of Dimopoulos, Magirou and Papadimitriou invoked in Section 4, immediately before Theorem 3, of [Kröll, Pichler and Woltran](https://www.ijcai.org/Proceedings/2017/0159.pdf). Their kernel convention is precisely an independent set that attacks every vertex outside it, so it agrees with the definition above.
Let \(G=(V_0\dot\cup V_1,R)\) be an instance of that problem, with \(V=\{v_1,\ldots,v_n\}\) and \(n\geq1\). Keep the graph unchanged and make its vertices the explicitly listed types. If a bipartition is not supplied, one can find it by a standard bipartiteness search on the underlying undirected graph.
Set \(q=\lceil\log_2 n\rceil\), and assign
\(\mu_{v_i}=2^{-q}\) for \(1\leq i<n\), and \(\mu_{v_n}=(2^q-n+1)2^{-q}\).
These are positive dyadic rationals: \(2^q\geq n\), so the last numerator is at least one. Their sum is
\(\sum_{i=1}^{n}\mu_{v_i}=(n-1)2^{-q}+(2^q-n+1)2^{-q}=1.\)
Each mass has binary encoding length \(O(1+\log n)\), so the complete mass list has polynomial length. The support size is exactly \(\tau=n\); no implicit collection of additional types is used. Bipartiteness and strong connectivity are preserved because the graph is unchanged.
Finally, choose the unary threshold \(k=3\). By the bijection proved above,
\(N\geq3\quad\Longleftrightarrow\quad G\text{ has more than two stable extensions}.\)
This is a polynomial many-one reduction, proving hardness even for fixed \(k=3\).
A certificate for \(N\geq k\) consists of \(k\) distinct subsets \(S_1,\ldots,S_k\subseteq T\), each encoded by a bit vector of length \(\tau\).
For each subset, scan the attacks to verify conflict-freeness and mark all vertices attacked from that subset. Then check that every vertex outside it is marked. This verifies stability in \(O(m+\tau)\) time. Pairwise comparisons verify distinctness in \(O(k^2\tau)\) time.
Because \(k\) is unary, both the certificate length \(k\tau\) and this verification time are polynomial in the input length. The bijection makes the certificate equivalent to \(k\) distinct feasible vectors. Thus the unary-threshold problem belongs to \(\mathrm{NP}\), and is \(\mathrm{NP}\)-complete.
Suppose an exact enumeration algorithm exists with total runtime bounded by
\(C(1+m+\tau+L+N)^d\)
for fixed positive integers \(C,d\). Any polynomial runtime bound can be enlarged to this form.
Given a threshold instance, simulate the enumerator for
\(B=C(1+m+\tau+L+k)^d\)
steps.
If it terminates within that budget, count its outputs and compare the count with \(k\). If it has not terminated, then necessarily \(N>k\): otherwise its total runtime bound would be at most \(B\). In that case, answer yes.
Since \(k\) is unary, this simulation takes polynomial time in \(m,\tau,L,k\). It would therefore solve the \(\mathrm{NP}\)-complete threshold problem in polynomial time, implying \(\mathrm{P}=\mathrm{NP}\).
This argument uses only the total runtime bound; it does not assume polynomial delay between outputs.
Assume \(\mathrm{P}=\mathrm{NP}\). Given a prefix of a candidate support bit vector, deciding whether it extends to a stable extension belongs to \(\mathrm{NP}\): guess the remaining bits and verify stability as above. Under the assumption, this completion question is decidable in polynomial time.
Enumerate support bit vectors by depth-first search, retaining exactly the prefixes for which completion is possible. Every retained prefix belongs to at least one stable extension. Therefore, when \(N>0\), the number of retained prefixes is at most \((\tau+1)N\). Each retained nonterminal prefix generates at most two completion queries. If \(N=0\), the root query rejects and the search ends.
Thus enumeration makes \(O(1+\tau N)\) polynomial-time completion queries. Each completed support is converted to its mass vector by copying the corresponding input masses, taking \(O(L+\tau)\) time. The resulting total runtime is polynomial in \(m,\tau,L,N\).
This proves the claimed equivalence and settles the stated complexity question.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The unary-threshold problem is \(\mathrm{NP}\)-complete even for the fixed threshold \(k=3\), and exact enumeration is possible in total output-polynomial time if and only if \(\mathrm{P}=\mathrm{NP}\). No major or minor mathematical issues were found.
Correct. If \(0<x_u<\mu_u\), the second feasibility condition supplies an incoming attacker \(t\) with \(x_t>0\). This violates the first condition because \(x_u>0\). The coordinate bounds then leave precisely the two possibilities \(x_u=0\) and \(x_u=\mu_u\).
The correspondence is verified in both directions:
Positivity of the masses is used explicitly and correctly. Consequently, the count is finite, bounded by \(2^\tau\), and independent of the particular positive masses.
Correct and verified. Section 4 of [Kröll, Pichler and Woltran](https://www.ijcai.org/Proceedings/2017/0159.pdf), immediately before Theorem 3, states that deciding whether a directed graph has more than two kernels is \(\mathrm{NP}\)-complete, including for bipartite graphs with a single strongly connected component.
That passage defines a kernel using independence and outgoing domination: every outside vertex receives an edge from a member of the kernel. Its orientation therefore agrees exactly with the prover’s stable-extension definition. The paper also explicitly identifies these kernels with stable extensions.
The cited theorem has the required graph restriction and threshold. There is no unverified change of convention or stronger theorem being assumed.
Correct. The reduction leaves the graph unchanged, supplies its bipartition if necessary, and assigns explicitly listed positive dyadic masses.
For \(n\geq1\), the choice \(q=\lceil\log_2 n\rceil\) ensures that the last numerator \(2^q-n+1\) is positive. The displayed sum equals one exactly. All numerators and denominators have binary length \(O(1+\log n)\), so the added input length is polynomial.
The boundary case \(n=1\) is covered: \(q=0\), the first mass range is empty, and the sole mass equals one.
The support size is exactly \(n\), and the graph restrictions remain intact. The correspondence from Section 1 establishes precisely the required equivalence between having at least three feasible vectors and having more than two stable extensions. Thus this is a valid polynomial many-one reduction with fixed unary threshold \(k=3\).
Correct. The proposed certificate contains \(k\) support bit vectors, with total length \(k\tau\). Each stability test checks both conflict-freeness and domination in \(O(m+\tau)\) time. Pairwise comparisons ensure that the witnesses represent distinct solutions in \(O(k^2\tau)\) time.
Because the threshold is unary, these bounds are polynomial in the threshold-instance length. The correspondence makes support certificates sufficient even though the original coordinates are allowed to be real.
If fewer than \(k\) solutions exist, no collection of \(k\) distinct valid certificates can pass verification. This includes thresholds larger than \(2^\tau\).
Correct. The assumed runtime bound is monotone in the solution count. If \(N\leq k\), the enumerator must terminate within the stated budget \(B\). Therefore, nontermination by that deadline implies \(N>k\), which justifies answering yes.
If the enumerator terminates within the budget, its complete output determines the answer by direct counting. Both branches are correct, including the boundary \(N=k\).
The fixed constants in the enumerator’s polynomial bound may be built into the resulting decision algorithm. Unary encoding of \(k\) makes the budget polynomial in the threshold-instance length. This argument requires a bound on total runtime only; it does not assume polynomial delay.
Correct. The prefix-completion question belongs to \(\mathrm{NP}\), since the remaining support bits form a certificate whose stability is polynomially verifiable. The assumed equality therefore supplies a polynomial-time completion test.
The search retains exactly prefixes that can lead to solutions. Each solution has \(\tau+1\) prefixes, giving the stated upper bound \((\tau+1)N\) on retained prefixes when \(N>0\). Rejected children add at most two queries per retained nonterminal prefix. The root rejection handles \(N=0\).
Every complete retained support is output once, and copying its input masses gives an exact finite representation of the corresponding vector. The query count and output conversion cost establish the claimed total polynomial bound.
No additional clarification, missing lemma, or mathematical repair is required.
⟨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.