Answer: —
Theorem 3.1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAlgorithm 1 solves Multiple-bit CSL with normal-form games in log2 n + 2 rounds.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(T=\{1,\ldots,\tau\}\), known rational masses \(\mu\in\mathbb{Q}_{>0}^{\tau}\) with \(\sum_t\mu_t=1\), and an unknown partition \(\Pi\) of \(T\) such that all replicas of each type lie in one coalition block, design adaptive succinct type-symmetric normal-form queries. A query indexed by \(E\subseteq T\times T\) uses directed-prisoner's-dilemma factors with payoffs normalized so that \(b\) deviates exactly when some \((a,b)\in E\) has \(a\sim_\Pi b\), returning \(\delta_b^E=\mu_b\mathbf{1}[\exists a:(a,b)\in E,\ a\sim_\Pi b]\); recover \(\Pi\) exactly while minimizing worst-case rounds.
A society is given by its support: \(T=\{1,\ldots,\tau\}\), with positive binary-rational masses \(\mu_t\) summing to \(1\). Here \(\tau\) counts supported types, and \(L\) is their total encoding length. An unknown partition \(\Pi\) has nonempty blocks; the entire mass of each type belongs to one block. Write \(a\sim_\Pi b\) for membership in the same block.
A query is specified succinctly by a list \(E\subseteq\{(a,b)\in T^2:a\ne b\}\). For each factor \((a,b)\), type \(b\) chooses \(C\) or \(D\); choosing \(C\) gives per-unit-mass payoffs \(2/\mu_a\) to type \(a\) and \(-1/\mu_b\) to type \(b\), while \(D\) gives zero. Other types have only the action \(D\). All replicas of a type use the same factor action.
Products use independent action coordinates and additive payoffs, with the all-\(D\) profile specified. Each coalition maximizes its integrated total payoff against outsiders retaining their specified actions; if the specified actions are already optimal, it retains them, and otherwise ties among best responses are adversarial.
One round returns the exact vector \(\delta^E\), where \(\delta_b^E=\mu_b\mathbf{1}[\exists a:(a,b)\in E\text{ and }a\sim_\Pi b]\). Only these product queries are permitted; successive queries may depend on previous observations.
Let \(R(\mu)\) be the minimum, over deterministic adaptive strategies recovering every possible \(\Pi\) exactly, of their worst-case number of rounds. The round-budget decision problem takes the support, masses, and a binary-encoded integer \(r\ge0\), and asks whether \(R(\mu)\le r\). State computational running times in \(m,\tau,L,\log(r+1)\), where \(m\) is the maximum number of listed factors per query, with no additional cap imposed.
Is the round-budget decision problem solvable in polynomial time, or is it NP-hard?
For finite societies of \(n\) agents, normal-form multiple-bit coalition learning admits recovery within \(\log_2 n+2\) rounds and requires \(\log_2 n-O(\log\log n)\) rounds in the worst case. [Verified source](https://arxiv.org/html/2412.10636v1)
No result settling the exact round-budget decision problem for this mass model was located.
The exact complexity classification remains unresolved. I prove a stronger recovery bound than the one in the notes:
$$ R(\mu)=R_\tau\le \lfloor\log_2\tau\rfloor. $$
In particular, the previously unsettled cases satisfy $R_6=R_7=2$.
I also repair the encoding convention in the hardness argument and prove that, under polynomial-time many-one reductions,
$$ \text{the round-budget problem is }\mathsf{NP}\text{-hard} \quad\Longleftrightarrow\quad \mathsf P=\mathsf{NP}. $$
This equivalence does not establish a uniform polynomial-time algorithm.
For each query $E$ and type $b$, define
$$ S_b(E)=\{a:(a,b)\in E\}. $$
Because $\mu_b>0$, the returned vector determines precisely the bits
$$ y_b^E=\mathbf 1[\delta_b^E>0] =\mathbf 1[S_b(E)\cap[b]_\Pi\ne\varnothing]. $$
Conversely, the bits determine the vector through $\delta_b^E=\mu_b y_b^E$.
The payoff specification introduces no further uncertainty. In a factor $(a,b)$, choosing $C$ changes the integrated payoff of the coalition containing $b$ by $2-1=1$ if it also contains $a$, and by $-1$ otherwise. Independent coordinates and additive payoffs therefore make each factor choice strictly optimal. Adversarial tie-breaking has no effect.
A strategy for one positive mass vector can consequently be used for any other positive mass vector on the same support: translate observations into bits and, when needed, translate those bits into the other mass-valued observations. This preserves every decision and the number of rounds. Thus the optimum depends only on $\tau$; denote it by $R_\tau$.
There are only
$$ M=\tau(\tau-1) $$
possible factors. Hence every permitted query has at most $M$ factors, intrinsically, without imposing an additional cap.
Given block labels for a partition, a query containing at most $m$ factors can be evaluated in
$$ O\!\left((m+\tau)\log(\tau+1)+L\right) $$
bit operations: inspect its factors, compute the response bits, and write the corresponding masses.
For every $\tau\ge1$,
$$ R_\tau\le\lfloor\log_2\tau\rfloor. $$
For $\tau=1$, there is only one partition, so no query is necessary. Assume henceforth that $\tau\ge2$, and put
$$ h=\lfloor\tau/2\rfloor. $$
Arrange the types in the cyclic order $1,\ldots,\tau$. Let $c_b(d)$ denote the type $d$ positions before $b$ in this order, for $1\le d\le h$.
For each $b$, determine
$$ d_b=\min\{d\in\{1,\ldots,h\}:c_b(d)\sim_\Pi b\}, $$
using the sentinel $h+1$ if this set is empty.
Each $d_b$ initially has $h+1$ ordered possibilities. Maintain an interval of possible values. If its size is $s>1$, query its first $\lfloor s/2\rfloor$ values by listing the corresponding factors $(c_b(d),b)$.
The queried prefix never contains the sentinel, because the sentinel is the largest possibility. Moreover, the maintained interval contains the true minimum $d_b$. Therefore the response at coordinate $b$ is positive exactly when $d_b$ belongs to the queried prefix. The surviving interval has size at most $\lceil s/2\rceil$.
All these searches run simultaneously: each search controls a different response coordinate. After
$$ k=\lceil\log_2(h+1)\rceil $$
rounds, every $d_b$ is known.
Construct an undirected graph $G$ by adding the edge $\{b,c_b(d_b)\}$ whenever $d_b\le h$.
Every added edge has endpoints in the same true block, so no connected component crosses blocks.
Fix a block $B$ with at least two members. List its members in cyclic order. Let $g_1,\ldots,g_q$ be the positive cyclic gaps between consecutive members, where $q=|B|$. Then
$$ \sum_{i=1}^{q}g_i=\tau. $$
For a member whose preceding block member is at distance $g_i$, that preceding member is its nearest matching predecessor. Consequently:
At most one gap can exceed $h$. Indeed, two such gaps would have sum at least $2(h+1)$, but
$$ 2(h+1)>\tau. $$
Thus $G[B]$ contains all the edges between consecutive cyclic members except possibly one. Those edges form a connected graph: a cycle, or a path after deleting one cyclic edge. For a two-member block, at least one of the two cyclic gaps supplies its connecting edge. A singleton has no matching predecessor and remains isolated.
Therefore the connected components of $G$ are exactly $\Pi$.
Finally, $k=\lfloor\log_2\tau\rfloor$. To check this without rounding ambiguity, let $j=\lfloor\log_2\tau\rfloor$. Since $\tau\ge2$,
$$ 2^j\le\tau\le2^{j+1}-1, $$
and hence
$$ 2^{j-1}+1\le h+1\le2^j. $$
Taking the ceiling of the base-two logarithm gives $k=j$, completing the proof.
Let $m$ be the largest factor list used by this strategy. Binary-search maintenance, query construction, response processing, and final graph reconstruction take altogether
$$ O\!\left( \lfloor\log_2\tau\rfloor \bigl((m+\tau)\log(\tau+1)+L\bigr) \right) $$
bit operations. This is polynomial because $m\le\tau(\tau-1)$.
For every $\tau\ge1$,
$$ R_\tau\le R_{\tau+1}. $$
To prove this, simulate a strategy on $\tau+1$ types while declaring the extra type a singleton. Delete all query factors involving that type. Such factors would never produce a positive response. Feed the simulated strategy the original response bits followed by a zero bit. Its final partition, restricted to the original support, recovers every partition on $\tau$ types.
Let $B_\tau$ be the number of partitions of $\tau$ labelled types. A query returns at most $2^\tau$ different bit vectors. A deterministic strategy using at most $r$ rounds therefore has at most $2^{\tau r}$ terminal transcripts.
Exact recovery requires distinct terminal transcripts for distinct partitions. Consequently,
$$ B_\tau\le2^{\tau r}, \qquad R_\tau\ge \left\lceil\frac{\log_2 B_\tau}{\tau}\right\rceil. $$
For completeness, Bell numbers can be computed from
$$ B_0=1, \qquad B_{s+1}=\sum_{j=0}^{s}\binom{s}{j}B_{s-j}. $$
Here $j$ counts the other members of the block containing the last element; the remaining elements can be partitioned in $B_{s-j}$ ways. This recurrence gives
$$ B_1=1,\quad B_2=2,\quad B_3=5,\quad B_4=15, $$
and
$$ B_5=15+4\cdot5+6\cdot2+4\cdot1+1=52>2^5. $$
Thus $R_5\ge2$. Monotonicity gives $R_6,R_7\ge2$, while the circular strategy gives an upper bound of two for all three supports. Therefore
$$ R_5=R_6=R_7=2. $$
The same upper bound gives $R_8\le3$, while monotonicity gives $R_8\ge2$. Thus the next case remains
$$ R_8\in\{2,3\}. $$
Define
$$ N_r=\max\{\tau:R_\tau\le r\}. $$
This maximum exists, as the following proof also establishes.
The circular strategy gives
$$ N_r\ge2^{r+1}-1. $$
For an upper bound, fix $r\ge0$, and set
$$ q=2^{r+1}, \qquad n=(r+1)q+1. $$
Consider partitions in which types $1,\ldots,q$ belong to distinct blocks, and every remaining type is assigned to exactly one of these $q$ blocks. There are precisely $q^{n-q}$ such partitions: each assignment is recoverable from the resulting partition by inspecting which distinguished type shares its block.
Their number satisfies
$$ q^{n-q} =2^{(r+1)(n-q)} =2^{rn+1} >2^{rn}. $$
The counting bound therefore excludes recovery of all partitions on $n$ types in $r$ rounds. Monotonicity excludes every larger support as well. Hence
$$ 2^{r+1}-1\le N_r\le(r+1)2^{r+1}. $$
In particular, $N_r$ is finite. Also, $N_0=1$, since every support of size at least two admits more than one partition.
The exact-budget question is equivalently whether $\tau\le N_r$. The displayed bounds do not determine these thresholds exactly.
Throughout this section, $\mathsf{NP}$-hardness means hardness under polynomial-time many-one reductions.
Let $\mathcal B$ be the language of valid society-and-budget encodings satisfying $R(\mu)\le r$. Malformed encodings are rejected. Validity, including positivity of rational masses and their exact sum being one, is checkable in polynomial time using integer arithmetic.
Put
$$ U_\tau=\lfloor\log_2\tau\rfloor. $$
Using canonical binary representations, define
$$ S=\{00\}\cup \{1^\tau0\operatorname{bin}(r): \tau\ge1,\ 0\le r<U_\tau,\ R_\tau\le r\}. $$
There is a total polynomial-time many-one reduction from $\mathcal B$ to $S$:
The second case is correct by the circular recovery bound. The third is correct by mass independence and the definition of $S$. Writing $\tau$ in unary costs polynomial time because the input explicitly lists $\tau$ positive masses.
The language $S$ is sparse. Among strings of length at most $s$, it has at most
$$ 1+\sum_{\tau=1}^{s}U_\tau =O(s\log(s+1)) $$
members.
Mahaney’s theorem states that a sparse language cannot be $\mathsf{NP}$-hard under polynomial-time many-one reductions unless $\mathsf P=\mathsf{NP}$; membership of that language in $\mathsf{NP}$ is not required. This is the form stated in [Theorem 2.1 of Grochow’s exposition](https://arxiv.org/html/1610.05825v1).
If $\mathcal B$ were $\mathsf{NP}$-hard, composition with the reduction above would make the sparse language $S$ $\mathsf{NP}$-hard. Therefore
$$ \mathcal B\text{ is }\mathsf{NP}\text{-hard} \quad\Longrightarrow\quad \mathsf P=\mathsf{NP}. $$
Conversely, suppose $\mathsf P=\mathsf{NP}$. There is a fixed valid yes-instance consisting of two masses $1/2,1/2$ and budget one, and a fixed valid no-instance with the same masses and budget zero. Every language in $\mathsf{NP}$ can then be decided in polynomial time and reduced to $\mathcal B$ by outputting the appropriate fixed instance.
Thus
$$ \mathcal B\text{ is }\mathsf{NP}\text{-hard} \quad\Longleftrightarrow\quad \mathsf P=\mathsf{NP}. $$
The following procedure establishes decidability and a polynomial-space upper bound, but its running time is exponential.
For a history $H$ of queries and bit responses, let $\mathcal P(H)$ be its consistent partitions. Define $W(H,d)$ to mean that this family can be recovered using at most $d$ further rounds.
The exact recurrence is:
$$ W(H,d) \quad\Longleftrightarrow\quad \exists E\ \forall y\in\{0,1\}^{\tau}\, W(H\mathbin{\|}(E,y),d-1). $$
The existential choice is the next deterministic query. The universal choice checks every response. A response inconsistent with every candidate partition yields an empty family and is vacuously successful. Induction on $d$ proves that this recurrence exactly characterizes recoverability.
First reject malformed inputs and accept valid inputs with $r\ge U_\tau$. Otherwise the recursion depth is less than $\log_2\tau$.
Candidate partitions need not be stored as a family. Enumerate canonical block-label sequences and test their consistency with the history, stopping after finding two when checking whether the family has size at most one. There are at most $\tau^\tau$ sequences to inspect, and one partition requires $O(\tau\log(\tau+1))$ bits.
Each query has an $M$-bit mask, where $M=\tau(\tau-1)$, and each response has $\tau$ bits. Depth-first evaluation therefore uses polynomial space in $\tau,L,\log(r+1)$.
There are $2^M$ possible queries and $2^\tau$ possible responses. The resulting deterministic running-time bound is
$$ \operatorname{poly}\!\bigl(\tau,L,\log(r+1)\bigr) \,2^{O(\tau^2\log(\tau+1))}. $$
Equivalently, expressing the enumeration cost using its maximum list size $m=M$, it is
$$ \operatorname{poly}\!\bigl(m,\tau,L,\log(r+1)\bigr) \,2^{O((m+\tau)\log(\tau+1))}. $$
Every permitted query is considered; no additional factor cap is imposed.
There is also a polynomial-time decision algorithm using $O(\log^2(N+1))$ bits of advice for inputs of total encoding length $N$.
Indeed, $\tau\le N$. Let $K=\lfloor\log_2N\rfloor$, and provide the truncated thresholds
$$ \min(N_r,N),\qquad 0\le r<K, $$
as advice. There are $K$ entries, each requiring $O(\log(N+1))$ bits.
After validating the input, accept immediately if $r\ge K$, because $R_\tau\le\lfloor\log_2\tau\rfloor\le K$. Otherwise compare $\tau$ with the advised threshold for $r$. Monotonicity and the definition of $N_r$ prove correctness.
This establishes polynomial-time solvability with short advice. It does not establish a uniform algorithm: the proofs above do not compute those advice thresholds in polynomial time.
The unresolved target is therefore the uniform complexity of the exact comparison $R_\tau\le r$. The circular strategy improves the sufficient budget and settles two additional cases, but does not prove optimality for general supports.
⟨structured verdict parsed — rendered above⟩
Overall assessment: partial, with substantial correct results. The prover establishes mass independence, the circular recovery bound, the stated exact small cases, finite threshold bounds, the conditional hardness equivalence, an exact polynomial-space procedure, and a short-advice algorithm. None of these settles the uniform polynomial-time versus $\mathsf{NP}$-hardness question in USER_TASK.
I found no false central mathematical step. There is one minor boundary defect in the recovery algorithm’s running-time bound.
This reduction is correct.
Because every mass is positive, the exact observation determines the bit
$$
y_b^E=\mathbf 1[\delta_b^E>0].
$$
Conversely, the known mass and this bit determine $\delta_b^E$. Thus translating between observations for two mass vectors on the same support preserves the information available to a deterministic adaptive strategy.
The payoff calculation is also correct. In a factor $(a,b)$, changing $b$’s action to $C$ changes its coalition’s integrated payoff by:
Independent action coordinates and additive payoffs make these choices strictly optimal coordinate by coordinate. Tie-breaking introduces no uncertainty here.
Consequently, the conclusion
$$
R(\mu)=R_\tau
$$
is justified. The intrinsic factor bound
$$
m\le \tau(\tau-1)
$$
also follows from the permitted query domain.
The query-evaluation bound is consistent with storing block labels using $O(\log(\tau+1))$ bits per type and copying the explicitly encoded masses into the response.
The construction and correctness proof are sound.
The important point is that the queried prefix is a prefix of the maintained interval, rather than necessarily a prefix beginning at distance one. The stated invariant is sufficient:
The sentinel cannot occur in a proper initial half of the interval because it is the largest possible value. Therefore every listed factor is valid.
Each update leaves at most $\lceil s/2\rceil$ possibilities, and the searches use distinct response coordinates. The simultaneous search therefore determines all $d_b$ within
$$
k=\lceil\log_2(h+1)\rceil
$$
rounds.
Every added edge joins members of the same true block.
For a nonsingleton block, its preceding member in cyclic block order is precisely its nearest matching predecessor. The cyclic gaps are positive and sum to $\tau$. Two gaps exceeding $h$ would have total at least
$$
2(h+1)>\tau,
$$
which is impossible.
Thus all consecutive cyclic block connections except possibly one are present. These connections yield a connected graph. The prover explicitly handles the two-member case, where the two cyclic connections represent the same undirected edge, and the singleton case.
The connected components therefore recover exactly the unknown partition.
For $\tau\ge2$, the displayed inequalities
$$
2^{j-1}+1\le h+1\le2^j,
\qquad j=\lfloor\log_2\tau\rfloor,
$$
correctly imply
$$
\lceil\log_2(h+1)\rceil=j.
$$
The separate zero-round argument for $\tau=1$ is correct.
Accordingly,
$$
R_\tau\le\lfloor\log_2\tau\rfloor
$$
is proved.
The stated total running-time bound has a factor $\lfloor\log_2\tau\rfloor$. At $\tau=1$, it is identically zero, although returning the recovered partition requires some work.
Minimum clarification: restrict this bound to $\tau\ge2$ and state the base-case cost separately, or include an additive initialization/output term. This does not affect the recovery theorem.
The singleton-extension simulation is valid. Any factor involving the extra singleton has no matching endpoints, so deleting those factors preserves every original response coordinate; the extra coordinate is zero.
Restricting the simulated final partition to the original support proves
$$
R_\tau\le R_{\tau+1}.
$$
Each query has at most $2^\tau$ outcomes. A deterministic decision tree of depth at most $r$ therefore has at most $2^{\tau r}$ leaves, including when some branches stop early.
Distinct partitions must reach distinct terminal leaves. Hence
$$
R_\tau\ge
\left\lceil\frac{\log_2 B_\tau}{\tau}\right\rceil
$$
is justified.
The Bell-number recurrence correctly counts partitions according to the other members of the last element’s block. The numerical computation
$$
B_5=15+20+12+4+1=52>32
$$
is correct.
Combining this bound with monotonicity and the circular strategy proves
$$
R_5=R_6=R_7=2.
$$
The stated bounds
$$
R_8\in\{2,3\}
$$
also follow. They do not decide which value occurs.
The lower bound follows directly from the circular strategy.
For the upper bound, the distinguished types label distinct blocks, so the $q^{n-q}$ assignments produce distinct partitions. With the stated choices of $q$ and $n$, the critical exponent calculation is correct:
$$
(r+1)(n-q)-rn=n-(r+1)q=1.
$$
Thus their number exceeds $2^{rn}$, excluding recovery in $r$ rounds at that support size.
Monotonicity excludes all larger supports. Together with the nonempty lower range, this proves the maximum exists and establishes
$$
2^{r+1}-1\le N_r\le(r+1)2^{r+1}.
$$
The separate conclusion $N_0=1$ is correct.
The reduction and theorem application are correct under the explicitly stated convention of polynomial-time many-one reductions.
Rejecting malformed encodings makes $\mathcal B$ a language on all strings. Checking explicit rational positivity and an exact sum of one is polynomial-time integer arithmetic.
The reduction to $S$ correctly handles every input:
Writing the support size in unary is polynomial-time because the input explicitly lists all supported types.
The sparsity estimate is valid: for each $\tau$, there are at most $U_\tau$ eligible budgets, giving polynomially many members of bounded length.
The cited theorem indeed applies to sparse $\mathsf{NP}$-hard languages without assuming that the sparse language belongs to $\mathsf{NP}$. Its proof explicitly uses polynomial-time many-one reductions. [Grochow, Theorem 2.1](https://arxiv.org/html/1610.05825v1)
Therefore the implication
$$
\mathcal B\text{ is }\mathsf{NP}\text{-hard}
\Longrightarrow
\mathsf P=\mathsf{NP}
$$
is justified.
For the converse, the two fixed instances have the claimed answers: two types are recoverable in one round, while zero rounds cannot distinguish their two possible partitions. Under $\mathsf P=\mathsf{NP}$, deciding any source language and then selecting the corresponding fixed instance is a valid reduction.
The equivalence is consequently proved. It is a conditional hardness characterization, not an unconditional hardness result or a uniform polynomial-time algorithm.
The recurrence correctly describes deterministic adaptive recoverability.
Its base cases correctly include an empty consistent family. In the recursive case, one query must work for every realizable response; treating unrealizable responses as automatically successful is valid.
The circular bound permits immediate acceptance for large budgets, so exhaustive recursion is needed only at depth less than $\log_2\tau$.
Enumerating canonical block-label sequences allows consistency and family-size checks without storing the entire family. Query masks, responses, partition labels, and the recursion stack all require polynomial space.
The branching factors and depth support the stated time bound
$$
\operatorname{poly}\bigl(\tau,L,\log(r+1)\bigr)
\,2^{O(\tau^2\log(\tau+1))}.
$$
The candidate-partition enumeration contributes at most $2^{O(\tau\log(\tau+1))}$ per node, which is absorbed in that bound.
The formulation using $m=M$ is also correct. It does not impose an additional factor cap.
Thus decidability and a polynomial-space upper bound are established.
This argument is correct.
For inputs of length $N$, the explicitly listed support satisfies $\tau\le N$. The supplied thresholds require $O(\log^2(N+1))$ advice bits.
For budgets at least $K$, the circular bound justifies acceptance. For smaller budgets, monotonicity makes comparison with the truncated threshold exact.
This establishes a nonuniform polynomial-time algorithm. As the prover acknowledges, no polynomial-time method for generating the advice is provided, so this does not establish uniform polynomial-time solvability.
Major scope issue: the requested uniform complexity classification remains unresolved. This is explicitly acknowledged by the prover rather than concealed by an invalid inference.
The valid recovery algorithm only supplies a sufficient round budget. The exact decision procedure has exponential running time, and the advice algorithm is nonuniform. The hardness equivalence supplies neither an unconditional hardness result nor a uniform polynomial-time algorithm.
Minimum additional requirement to resolve USER_TASK: provide a rigorous uniform polynomial-time decision algorithm with its running-time analysis, or an unconditional hardness argument under a specified reduction notion. This requires further mathematics; it is not an expositional repair.
The references to “notes,” “previously unsettled cases,” and “two additional cases” cannot be verified from the supplied inputs. They are historical descriptions, not premises of the arguments, and do not affect the proved results.
⟨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.