Answer: \(\mathrm{NP}\)-hard under polynomial-time Turing reductions; more precisely, \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions.
Theorem 5 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateDUMMY is co-NP-complete for TCSG-T and WTSG-T.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite skills \(S\), tasks \(J\) with required sets \(R_j\subseteq S\), a threshold \(q\), supported types \(\Theta\) with bundles \(A_\theta\subseteq S\) and positive rational masses \(\mu_\theta\) summing to \(1\), and a target type \(\theta^\star\), decide whether for every subdistribution \(x\le\mu\) with \(x_{\theta^\star}=0\), \(V(x+\delta e_{\theta^\star})=V(x)\) for every \(0<\delta\le\mu_{\theta^\star}\). Here \(V(x)=1\) iff at least \(q\) tasks each have every required skill supplied by positive selected mass, and \(V(x)=0\) otherwise.
Given a finite skill set \(S\) and a list of tasks \(J\), each task \(j\) has an explicitly listed requirement set \(R_j\subseteq S\). Tasks with identical requirements count separately; empty requirements and empty skill bundles are allowed.
A society is given by its support: a list \(\Theta\) of \(\tau\) types with bundles \(A_\theta\subseteq S\) and positive binary rational masses \(\mu_\theta\), where \(\sum_\theta\mu_\theta=1\). Here \(\tau\) is the support size, not the number of possible types.
The input also specifies a binary integer threshold \(q\geq0\) and a target type \(\theta^\star\in\Theta\). Put \(m=|J|\), \(k=|S|\), and let \(L\) be the total input bit length; state running times in \(m,k,\tau,L\).
For any real subdistribution \(0\leq x\leq\mu\), define \(U(x)=\bigcup_{\theta:x_\theta>0}A_\theta\) and \(V(x)=\mathbf{1}\{\,|\{j\in J:R_j\subseteq U(x)\}|\geq q\,\}\). Skills are reusable across tasks.
Call the target type dummy if \(V(x+\delta e_{\theta^\star})=V(x)\) for every such \(x\) with \(x_{\theta^\star}=0\) and every real \(0<\delta\leq\mu_{\theta^\star}\), where \(e_{\theta^\star}\) is its coordinate unit vector.
Is deciding whether the target type is dummy in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard under polynomial-time Turing reductions?
Discrete dummy recognition for task-count skill games with a threshold is \(\mathrm{coNP}\)-complete; the [full version](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/CompCoopInCSG-AIJ.pdf) retains this result.
No result for exactly this mass-based dummy-recognition problem was located in the literature search.
Dummy recognition is \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions, and hence \(\mathrm{NP}\)-hard under polynomial-time Turing reductions. This holds even when every type has a distinct singleton bundle, all masses are equal, and every task requires at most two skills.
The discrete result in [Section 4.3 of the cited full version](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/CompCoopInCSG-AIJ.pdf) is consistent with this conclusion. Below is a direct proof for the exact mass-based formulation.
For a subset \(C\subseteq\Theta\), define its available skills and completed-task count by
\(B(C)=\bigcup_{\theta\in C}A_\theta,\qquad F(C)=|\{j\in J:R_j\subseteq B(C)\}|.\)
Lemma. The target is non-dummy if and only if there exists \(C\subseteq\Theta\setminus\{\theta^\star\}\) such that
\(F(C)<q\leq F(C\cup\{\theta^\star\}).\)
Proof. Suppose admissible \(x,\delta\) witness non-dummy status, and put \(C=\{\theta:x_\theta>0\}\). Since \(x_{\theta^\star}=0\), the target does not belong to \(C\). Moreover,
\(U(x)=B(C),\qquad U(x+\delta e_{\theta^\star})=B(C\cup\{\theta^\star\}).\)
Adding skills cannot decrease the completed-task count. Therefore, a change in value must be from losing to winning, which gives the stated inequalities.
Conversely, suppose such a subset \(C\) exists. Set \(x_\theta=\mu_\theta\) for \(\theta\in C\), and set all other coordinates to zero. These coordinates satisfy \(0\leq x\leq\mu\). Because every mass is positive, the support of \(x\) is exactly \(C\). Taking \(\delta=\mu_{\theta^\star}>0\) gives the two skill unions above, and hence changes the value from zero to one. This proves the lemma.
Thus the numerical mass values do not affect dummy status, provided they are positive.
The degenerate cases also follow immediately: if \(q=0\), if \(q>m\), or if \(A_{\theta^\star}=\varnothing\), the target is dummy.
A certificate of non-dummy status is the subset \(C\) in the lemma, encoded using \(\tau-1\) bits. Verification consists of forming two skill unions, counting completed tasks for each, and checking the inequalities.
Using characteristic vectors indexed by the explicitly listed skills, this requires \(O((\tau+m+1)(k+1))\) elementary set and counting operations, in addition to parsing the input. No arithmetic on the rational masses is needed.
For an explicit conservative bit-operation bound, put
\(H=L+(\tau+m+1)(k+1).\)
The verifier runs in \(O(H^2)\) bit operations: at most \(O(H)\) elementary operations are required, and their operands and indices have at most \(O(H)\) bits. Consequently, non-dummy recognition belongs to \(\mathrm{NP}\), and dummy recognition belongs to \(\mathrm{coNP}\).
Enumerating all subsets of the other types also gives a deterministic algorithm running in
\(O(2^{\tau-1}H^2)\)
bit operations. Here \(\tau\) is the listed support size.
Use the standard \(\mathrm{NP}\)-complete Independent Set problem: given a finite simple undirected graph \(G=(W,E)\) and an integer \(r\), decide whether \(G\) has an independent set of size at least \(r\).
We restrict to \(n=|W|\geq1\) and \(1\leq r\leq n\). This restriction preserves hardness: instances outside these bounds have immediate answers and can be mapped to fixed yes- or no-instances within the bounds.
Let \(e=|E|\). Construct the following society and task list.
All masses are positive binary rationals and sum to one. Repeated edge tasks are permitted by the input specification.
The constructed parameters are
\(k=\tau=n+1,\qquad m=n+(r+1)e+1.\)
Using indexed skill names, its bit length and construction time are bounded by
\(O((n+(r+1)e+1)\log(n+2)).\)
Because \(r\leq n\), the reduction has polynomial size and running time.
Let \(C\subseteq\Theta\setminus\{\theta^\star\}\), and associate with it the vertex subset
\(T=\{v\in W:\theta_v\in C\}.\)
Write \(t=|T|\), and let \(h\) be the number of edges whose two endpoints both belong to \(T\).
The coalition completes exactly \(t\) vertex tasks. For each of the \(h\) induced edges, it completes all \(r+1\) copies of the corresponding edge task. It does not complete the target task. Therefore,
\(F(C)=t+(r+1)h.\)
Adding the target completes exactly one additional task, since \(s_\star\) appears only in that task. Hence,
\(F(C\cup\{\theta^\star\})=F(C)+1.\)
By the support lemma, \(C\) witnesses non-dummy status precisely when
\(F(C)<r+1\leq F(C)+1.\)
Since \(F(C)\) is an integer, these inequalities are equivalent to \(F(C)=r\). Substituting the count gives
\(t+(r+1)h=r.\)
If \(h\geq1\), the left side is at least \(r+1\), a contradiction. Thus \(h=0\), and then \(t=r\). Consequently, every non-dummy witness determines an independent set of exactly \(r\) vertices.
Conversely, if \(G\) has an independent set of size at least \(r\), choose any \(r\) of its vertices. Their associated types give \(t=r\) and \(h=0\), so the coalition completes exactly \(r\) tasks. Adding the target increases this count to \(r+1=q\), establishing non-dummy status.
We have proved
\(G\text{ has an independent set of size at least }r \quad\Longleftrightarrow\quad \theta^\star\text{ is non-dummy}.\)
As a supplementary check, this equivalence was exhaustively verified for every labeled simple graph on at most five vertices and every \(1\leq r\leq n\), covering \(5405\) graph-threshold instances. The argument above proves it for all sizes.
The construction is a polynomial-time many-one reduction from Independent Set to non-dummy recognition. Together with membership in \(\mathrm{NP}\), this proves that non-dummy recognition is \(\mathrm{NP}\)-complete.
Taking complements of the same equivalence proves that dummy recognition is \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions.
Finally, an Independent Set algorithm can construct this instance, make one call to a dummy-recognition oracle, and negate its answer. This is a polynomial-time Turing reduction, proving the requested \(\mathrm{NP}\)-hardness. In particular, a polynomial-time algorithm for dummy recognition would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly. Dummy recognition is \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions and therefore \(\mathrm{NP}\)-hard under polynomial-time Turing reductions. I found no major or minor mathematical issues.
The support lemma correctly handles both directions and all quantifiers.
Given a non-dummy witness \(x,\delta\), its support \(C\) excludes \(\theta^\star\), because \(x_{\theta^\star}=0\). Positivity of \(\delta\) ensures that adding the target changes the skill union to exactly \(B(C\cup\{\theta^\star\})\). Task completion is monotone under adding skills, so unequal values must satisfy
\[
F(C)<q\leq F(C\cup\{\theta^\star\}).
\]
Conversely, the prescribed choice \(x_\theta=\mu_\theta\) on \(C\), with zero elsewhere, is admissible. Strict positivity of every mass makes its support exactly \(C\). Choosing \(\delta=\mu_{\theta^\star}\) satisfies the permitted range and keeps the augmented vector within \(\mu\).
Thus the existential subset condition is exactly the negation of the universally quantified dummy condition. No discretization assumption about real coordinates is introduced.
The three stated degenerate cases are correct:
Empty requirement sets cause no problem: their tasks are counted before and after adding the target. Repeated tasks are counted separately throughout. Empty bundles and overlapping bundles also preserve the support lemma.
The argument covers \(m=0\), \(k=0\), and \(\tau=1\). A designated target guarantees \(\tau\geq1\).
A subset of the other support types is a certificate using \(\tau-1\) bits. Forming both unions and testing every explicitly listed requirement set verifies the certificate in polynomial time.
The stated elementary-operation bound \(O((\tau+m+1)(k+1))\), after parsing and indexing skills, is sufficient. With
\[
H=L+(\tau+m+1)(k+1),
\]
the conservative bound \(O(H^2)\) accommodates parsing, indices, counters, and comparison with the binary threshold. Large numerical values of \(q\) do not require iteration up to \(q\).
No rational arithmetic is needed for dummy recognition on the valid inputs specified by the task. Hence non-dummy recognition belongs to \(\mathrm{NP}\), and dummy recognition belongs to \(\mathrm{coNP}\).
Enumerating the \(2^{\tau-1}\) candidate subsets gives the claimed \(O(2^{\tau-1}H^2)\) deterministic bound.
The invoked theorem is the standard \(\mathrm{NP}\)-completeness of deciding whether a finite simple undirected graph has an independent set of size at least a given integer. Its formulation matches the source problem used here. See the [MIT course notes on Independent Set](https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/1dee182d301235b901119a0ff57f05e2_MIT6_046JS15_Recitation8.pdf).
Restricting to \(n\geq1\) and \(1\leq r\leq n\) preserves hardness as stated: excluded instances have immediately determined answers, and the restricted domain contains fixed yes- and no-instances.
Every constructed instance satisfies the target input requirements. The masses \(1/(n+1)\) are positive binary-encoded rationals summing to one. Bundles are distinct singletons; task requirements have size at most two. The separately listed edge-task copies are expressly permitted.
The parameter counts
\[
k=\tau=n+1,\qquad m=n+(r+1)e+1
\]
are correct. Indexed identifiers and mass denominators require \(O(\log(n+2))\) bits each. The claimed construction bound is polynomial because \(r\leq n\).
For a vertex subset \(T\), the count
\[
F(C)=t+(r+1)h
\]
accounts for every constructed task: \(t\) vertex tasks, \(r+1\) copies for each induced edge, and no target task.
The target skill occurs only in its own singleton task, so adding the target increases the count by exactly one.
The witness inequalities therefore reduce correctly to \(F(C)=r\), using integrality. In
\[
t+(r+1)h=r,
\]
both \(t\) and \(h\) are nonnegative integers. Any \(h\geq1\) makes the left side exceed \(r\), so a witness necessarily has \(h=0\) and \(t=r\).
The converse also holds as written: selecting any \(r\) vertices from an independent set of size at least \(r\) produces the required witness.
I independently reproduced the supplementary exhaustive check. All \(5405\) graph-threshold instances passed. This computation corroborates the proof but is not needed for it.
The established equivalence is a many-one reduction from Independent Set to non-dummy recognition. Combined with membership, it proves \(\mathrm{NP}\)-completeness of non-dummy recognition. Complementing the same equivalence correctly establishes \(\mathrm{coNP}\)-completeness of dummy recognition.
A dummy oracle can decide Independent Set by one query followed by negation, which is precisely the requested polynomial-time Turing reduction. The consequence that a polynomial-time dummy algorithm would imply \(\mathrm{P}=\mathrm{NP}\) is valid.
The literature remark is accurate: Section 4.3, Theorem 7 of the [cited full version](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/CompCoopInCSG-AIJ.pdf) states the corresponding discrete threshold-game result. The direct proof does not depend on transferring that theorem.
Actionable feedback: No mathematical repair or additional clarification is needed.
⟨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.