Answer: —
Theorem 3.2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateIG solves the CSL problem with a sample complexity upper bounded by n log2 n + 3n.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(\tau\) rational-mass types with finite rational action and payoff descriptions, all copies of each type constrained to one unknown coalition block \(\Pi\), adaptively design factorized normal-form games and default type-action profiles, receive one bit indicating whether the profile is a Nash equilibrium under coalition aggregate payoff \(\sum_{t\in B}\mu_tu_t\), and recover \(\Pi\) with minimum worst-case queries.
A society is given by its support: the list of \(\tau\geq1\) labeled types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. An unknown partition \(\Pi\) assigns each entire type to one nonempty coalition; singleton coalitions are allowed, and the number of coalitions is unknown.
Each query freely specifies finitely many explicitly tabulated normal-form factors with nonempty finite action sets and arbitrary signed rational payoffs. A type's action is a tuple of its factor actions, its payoff \(u_t\) is the sum of its factor payoffs, and the query specifies a pure default profile \(a\). All mass of a type uses the same action, including during deviations.
The oracle returns one exactly when no block \(B\in\Pi\) can strictly increase \(\sum_{t\in B}\mu_tu_t(a)\) by jointly changing the actions of any or all of its types, holding other blocks fixed. Equal-payoff deviations do not invalidate equilibrium. Queries may depend on previous oracle answers; oracle calls have unit cost.
Let \(Q(\mu)\) be the minimum worst-case query count of a deterministic adaptive strategy that identifies every possible \(\Pi\) exactly. The computational input is the mass list and a binary integer budget \(q\geq0\). Let \(L\) be the input bit length; when describing query construction, let \(m\) be the maximum factor action-set size, \(k\) the number of factors, and \(L_G\) their total binary description length. State running times in these quantities and \(\tau\).
Is deciding whether \(Q(\mu)\leq q\) polynomial-time solvable in \(\tau,L\), or is it NP-hard?
For discrete agents, Iterative Grouping uses at most \(n\log_2 n+3n\) queries, while every exact single-bit learner needs at least \(\lceil\log_2 B_n\rceil=n\log_2 n-O(n\log_2\log_2 n)\), where \(B_n\) is the Bell number. These bounds concern query counts rather than computing the exact minimum. [Xu, Ling, and Fang](https://arxiv.org/html/2312.09058v2).
No result settling this precise mass-based, minimum-query problem was located.
The complexity classification remains unresolved. I prove that the masses have no effect on the optimum and that, under polynomial-time many-one reductions,
$$
\text{the decision problem is NP-hard}
\quad\Longleftrightarrow\quad
\mathsf P=\mathsf{NP}.
$$
This does not establish polynomial-time solvability.
Beyond repairing the sparse-language reduction in the notes, I establish two further exact cases:
$$
Q_5=6,\qquad Q_6=8.
$$
I also give an exhaustive algorithm with a substantially smaller running-time bound than enumerating all subfamilies of the partition universe.
Let
$$
T=\{1,\ldots,\tau\},
$$
and let $\mathcal P_\tau$ be the set of partitions of $T$. Write $B_\tau=|\mathcal P_\tau|$ for the Bell number.
A coalition is profitable in a query if it has a permitted deviation whose mass-weighted payoff gain is strictly positive.
Consider two positive normalized rational mass vectors $\mu$ and $\nu$ on the same labeled support. Given a query for $\mu$, replace every factor payoff by
$$
u'_{t,f}=\frac{\mu_t}{\nu_t}u_{t,f}.
$$
Keep all action sets and the default profile unchanged. For every coalition $C$ and every permitted deviation,
$$
\sum_{t\in C}\nu_t
\bigl(u'_t(a'_C,a_{-C})-u'_t(a)\bigr)
=
\sum_{t\in C}\mu_t
\bigl(u_t(a'_C,a_{-C})-u_t(a)\bigr).
$$
Thus the transformation preserves strict profitability, including deviations in which some coalition members retain their default actions. It consequently preserves the oracle answer for every partition.
Applying this transformation at every node of an adaptive strategy preserves its answer paths and its query count. Transforming in both directions proves
$$
Q(\mu)=Q(\nu).
$$
Relabeling the support also preserves the optimum. Hence there is a sequence $Q_\tau$, depending only on the support size, such that
$$
Q(\mu)=Q_\tau.
$$
Positivity of all masses is necessary for this argument: it ensures that every multiplier is defined.
Running time. Rescaling preserves the number $k$ of factors and the maximum action-set size $m$. It takes time polynomial in $\tau,L,L_G$ and the encoding length of $\nu$, by exact rational arithmetic. No expansion of the product action space is needed.
For a query $G$, define
$$
\mathcal F_G=
\left\{
C\subseteq T:
C\ne\varnothing
\text{ and }C\text{ is profitable in }G
\right\}.
$$
Whether $C$ is profitable depends on its members, the query, and the default actions outside $C$. It does not depend on the partition of those outside types.
The oracle therefore answers one exactly when
$$
\Pi\cap\mathcal F_G=\varnothing.
$$
Fix a nonempty subset $B\subseteq T$, and choose $r\in B$. Construct one factor in which $r$ has two actions, default and toggle, while every other type has one action.
All payoffs at the default profile are zero. At the toggle profile, set
$$
\mu_tu_t=
\begin{cases}
\frac32-|B|,&t=r,\\
1,&t\in B\setminus\{r\},\\
-1,&t\notin B.
\end{cases}
$$
These are rational payoffs because every $\mu_t$ is positive and rational.
A coalition not containing $r$ cannot change this factor’s profile. If $r\in C$, its gain from toggling is
$$
\begin{aligned}
\frac32-|B|
+|C\cap(B\setminus\{r\})|
-|C\setminus B|
&=
\frac12-|B\setminus C|-|C\setminus B|.
\end{aligned}
$$
For $C=B$, the gain is $\frac12$. For every other $C$ containing $r$, at least one of the two set differences is nonempty, so the gain is at most $-\frac12$. Thus this factor makes exactly $B$ profitable.
For an arbitrary family
$$
\mathcal F\subseteq 2^T\setminus\{\varnothing\},
$$
include one such factor for every $B\in\mathcal F$.
Factor actions can be chosen independently, and factor gains add. If a coalition has a positive-gain deviation in one factor, it can change only that factor. Conversely, a positive total gain must include a positive gain in at least one factor. Therefore the combined query has forbidden family exactly $\mathcal F$.
An all-zero factor implements the empty family.
Consequently, the available tests are exactly
$$
\Pi\longmapsto
\mathbf 1[\Pi\cap\mathcal F=\varnothing],
\qquad
\mathcal F\subseteq 2^T\setminus\{\varnothing\}.
$$
Construction costs. For nonempty $\mathcal F$, this construction has
$$
k=|\mathcal F|,\qquad m=2,
$$
and only two profiles per factor. Put
$$
s=L+\log_2(\tau+1).
$$
The description length is $O(k\tau s)$, and a conservative construction-time bound using elementary exact rational arithmetic is $O(k\tau s^3)$. The model permits $k$ to be exponential in $\tau$.
For completeness, the forbidden family of an arbitrary supplied query can also be computed by finite enumeration. For each factor, enumerate all nonempty coalitions and their factor deviations. The number of coalition-action pairs is at most
$$
\prod_{t\in T}(1+|A_{t,f}|)
\le (m+1)^\tau.
$$
The total time is therefore
$$
O\!\left(k(m+1)^\tau
\operatorname{poly}(\tau,L,L_G)\right).
$$
Checking factors separately suffices because a coalition can retain the default in every other factor, and a positive total gain requires some positive factor gain.
The following extension will be needed for the six-type construction.
For $S\subseteq T$, define the restricted partition
$$
\Pi|_S=
\{C\cap S:C\in\Pi,\ C\cap S\ne\varnothing\}.
$$
Its members are nonempty, disjoint, and cover $S$.
Fix $\varnothing\ne B\subseteq S$ and $r\in B$. Modify the preceding factor by assigning mass-weighted toggle payoffs
$$
\mu_tu_t=
\begin{cases}
\frac32-|B|,&t=r,\\
1,&t\in B\setminus\{r\},\\
-1,&t\in S\setminus B,\\
0,&t\notin S.
\end{cases}
$$
For a coalition containing $r$, the gain is
$$
\frac12-|B\setminus C|-|(C\cap S)\setminus B|.
$$
This is positive exactly when $C\cap S=B$. Coalitions excluding $r$ cannot change the profile.
Combining these factors realizes every test
$$
\mathbf 1[(\Pi|_S)\cap\mathcal F=\varnothing]
$$
for a family of nonempty subsets of $S$, with the same construction bounds as above.
A deterministic strategy using at most $q$ queries has at most $2^q$ answer leaves. Exact identification requires a distinct leaf for every partition. Hence
$$
Q_\tau\ge
\left\lceil\log_2 B_\tau\right\rceil.
$$
For distinct types $i,j$, give only $i$ a toggle action. At toggle, assign mass-weighted payoffs $-1$ to $i$, $2$ to $j$, and zero to every other type.
A coalition containing $i$ gains
$$
-1+2\mathbf 1[j\in C].
$$
Thus the oracle answers zero exactly when $i$ and $j$ belong to the same block. Testing all pairs gives
$$
Q_\tau\le h_\tau:=\binom{\tau}{2}.
$$
A stronger bound follows by insertion. Suppose the restriction to the first $i-1$ types has been identified and has $r$ blocks. Choose one representative from each block.
Type $i$ either joins one of those $r$ represented blocks or belongs to a block containing no earlier type. There are $r+1$ possibilities. Assign them distinct binary codes of length
$$
c=\left\lceil\log_2(r+1)\right\rceil,
$$
using the zero code for the last possibility.
For each bit, combine pair factors between $i$ and the representatives whose codes have that bit set. The oracle answers zero exactly when the correct representative has that bit. Indeed, the representatives belong to distinct actual blocks, so at most one can share a block with $i$.
The $c$ answers therefore identify the correct possibility. Induction gives
$$
Q_\tau\le U_\tau:=
\sum_{i=2}^{\tau}\left\lceil\log_2 i\right\rceil
\le
(\tau-1)\left\lceil\log_2\tau\right\rceil.
$$
Each insertion query has $m=2$ and at most $\tau-1$ factors. The whole strategy can be constructed and executed, excluding unit-cost oracle calls, in time polynomial in $\tau,L$.
The key is a six-bit code for partitions of five types with several partitions identifiable from the first five bits.
For a nonempty block $B\subseteq\{1,\ldots,5\}$, assign an integer code $c(B)$ between zero and $63$. Its binary expansion has six bits. The assignments are as follows; entries in each row correspond in order.
| Blocks | Codes |
|---|---|
| All singletons | $0$ |
| $\{1,2\},\{1,3\},\{1,4\},\{1,5\},\{2,3\}$ | $20,6,19,36,48$ |
| $\{2,4\},\{2,5\},\{3,4\},\{3,5\},\{4,5\}$ | $40,13,24,10,34$ |
| $\{1,2,3\},\{1,2,4\},\{1,2,5\},\{1,3,4\},\{1,3,5\}$ | $9,16,32,33,17$ |
| $\{1,4,5\},\{2,3,4\},\{2,3,5\},\{2,4,5\},\{3,4,5\}$ | $5,3,4,8,2$ |
| $\{1,2,3,4\},\{1,2,3,5\},\{1,2,4,5\},\{1,3,4,5\},\{2,3,4,5\}$ | $47,55,58,59,61$ |
| $\{1,2,3,4,5\}$ | $62$ |
Define the signature of a partition by bitwise OR:
$$
\sigma(\Pi)=\bigvee_{B\in\Pi}c(B).
$$
For each bit position, query the family of blocks whose codes contain that bit. By Section 2, the negated oracle answer is precisely that bit of $\sigma(\Pi)$.
The following table lists the signatures grouped by block sizes.
| Block sizes | Signatures |
|---|---|
| $1,1,1,1,1$ | $0$ |
| $2,1,1,1$ | $6,10,13,19,20,24,34,36,40,48$ |
| $2,2,1$ | $15,27,28,29,30,31,38,42,44,46,50,51,52,54,60$ |
| $3,1,1$ | $2,3,4,5,8,9,16,17,32,33$ |
| $3,2$ | $14,22,23,26,39,43,45,53,56,57$ |
| $4,1$ | $47,55,58,59,61$ |
| $5$ | $62$ |
For rows with only one nonsingleton block, the signature is its assigned code. The two remaining rows require OR calculations.
For the $2,2,1$ row, grouping by the remaining singleton gives:
$$
\begin{array}{c|ccc}
\text{Singleton}&\multicolumn{3}{c}{\text{Signatures}}\\
1&50&42&29\\
2&38&27&60\\
3&54&31&44\\
4&30&15&52\\
5&28&46&51
\end{array}
$$
For example, with singleton $1$, the three pairings give
$$
48\vee34=50,\qquad
40\vee10=42,\qquad
13\vee24=29.
$$
For the $3,2$ row, listing the pair and its complementary triple gives:
$$
\begin{array}{c|cccccccccc}
\text{Pair}&12&13&14&15&23&24&25&34&35&45\\
\text{Signature}&22&14&23&39&53&57&45&56&26&43
\end{array}
$$
Here, for example, $12$ denotes the pair $\{1,2\}$.
These calculations enumerate all partitions of five types. Every displayed signature is distinct, both within and between rows. There are
$$
1+10+15+10+10+5+1=52
$$
of them. Thus six nonadaptive queries identify every partition.
Since
$$
32<B_5=52\le64,
$$
the information lower bound proves
$$
\boxed{Q_5=6}.
$$
The unused six-bit signatures are exactly
$$
1,7,11,12,18,21,25,35,37,41,49,63.
$$
For the all-singleton partition and every partition with one pair and three singletons, toggling the least significant bit of its signature produces one of these unused values:
$$
\begin{array}{c|rrrrrrrrrrr}
\text{Signature}&0&6&10&13&19&20&24&34&36&40&48\\
\text{Toggled value}&1&7&11&12&18&21&25&35&37&41&49
\end{array}
$$
Two six-bit values have the same five most significant bits exactly when they are equal or differ only in the least significant bit. Consequently, each of these eleven partitions is identified by the five most significant bits alone.
Use the following adaptive strategy: query those five bits first. If their prefix identifies one of these eleven partitions, stop. Otherwise, query the remaining bit. This strategy uses:
First identify the restriction to the first five types using the preceding adaptive strategy. Section 2.3 makes all its queries available even when those five types share blocks with type $6$.
Let the identified restriction have $r$ blocks.
If $r\ge4$, the first stage uses five queries. Inserting type $6$ uses at most
$$
\left\lceil\log_2(r+1)\right\rceil\le3
$$
more queries.
If $r\le3$, the first stage uses at most six queries. Insertion uses at most
$$
\left\lceil\log_2(r+1)\right\rceil\le2
$$
more queries.
Both cases use at most eight queries. Identifying the restriction and the block joined by type $6$, or determining that it starts a new block, identifies the whole partition.
The Bell numbers satisfy
$$
B_0=1,\qquad
B_{n+1}=\sum_{j=0}^{n}\binom nj B_j.
$$
To justify this recurrence, choose the $j$ elements outside the block containing a designated element; their partition can be chosen in $B_j$ ways. It gives
$$
B_0,\ldots,B_6=1,1,2,5,15,52,203.
$$
Since
$$
128<203\le256,
$$
eight queries are necessary. Therefore
$$
\boxed{Q_6=8}.
$$
All queries in these five- and six-type constructions have $m=2$ and at most $26$ factors. Their construction time and description length are polynomial in $L$.
Let $A$ be the language of valid mass-list and budget encodings satisfying $Q(\mu)\le q$. Reject malformed encodings. Validity, including positivity and exact normalization, can be checked in polynomial time by rational arithmetic.
Here, NP-hardness means hardness under deterministic polynomial-time many-one reductions.
Define
$$
S=
\{\mathtt{YES}\}
\cup
\left\{
1^\tau\#\operatorname{bin}(q):
\tau\ge1,\ 0\le q<h_\tau,\ Q_\tau\le q
\right\},
$$
where binary integer encodings are canonical.
Given a valid instance of $A$:
Malformed instances map to a fixed string outside $S$.
The pair-test bound and mass invariance prove that this reduction preserves membership. Its output length is polynomial because the explicit mass list implies $\tau\le L$.
A language is sparse if its number of members of length at most $N$ is bounded by a polynomial in $N$. Here that number is at most
$$
1+\sum_{\tau=1}^{N}h_\tau=O(N^3).
$$
Thus $S$ is sparse.
Mahaney’s theorem states that a sparse language cannot be NP-hard under polynomial-time many-one reductions unless $\mathsf P=\mathsf{NP}$. The sparse language need not itself belong to $\mathsf{NP}$. This formulation is given in [Grochow’s exposition](https://arxiv.org/abs/1610.05825).
If $A$ were NP-hard, composing its hardness reductions with the reduction to $S$ would make $S$ NP-hard. The theorem therefore applies and yields
$$
A\text{ is NP-hard}\Longrightarrow\mathsf P=\mathsf{NP}.
$$
The reverse reduction must treat the budget restriction as part of membership in $S$.
Map $\mathtt{YES}$ to the one-type instance with mass $1$ and budget zero. Map every string failing the required syntax, or satisfying $q\ge h_\tau$, to the two-type instance with masses $\frac12,\frac12$ and budget zero. This is a no-instance because there are two possible partitions.
For a remaining string $1^\tau\#\operatorname{bin}(q)$, put
$$
d=\left\lceil\log_2\tau\right\rceil
$$
and construct
$$
\mu_t=2^{-d}\quad(1\le t<\tau),\qquad
\mu_\tau=\frac{2^d-\tau+1}{2^d}.
$$
All masses are positive, since $2^d\ge\tau$, and
$$
\sum_{t=1}^{\tau}\mu_t
=
\frac{\tau-1+2^d-\tau+1}{2^d}=1.
$$
They are dyadic rationals with total description length $O(\tau\log_2(\tau+1))$. Mass invariance proves that the resulting instance is in $A$ exactly when the original string is in $S$.
Thus $A$ and $S$ are polynomial-time many-one equivalent. In particular, syntactically valid strings with $q\ge h_\tau$ map to no-instances, repairing the issue identified by the verifier.
Conversely, if $\mathsf P=\mathsf{NP}$, satisfiability can be decided in polynomial time. Decide a satisfiability instance and output either the fixed yes-instance or the fixed no-instance above. This gives a polynomial-time many-one reduction from satisfiability to $A$.
Hence
$$
\boxed{
A\text{ is NP-hard}
\quad\Longleftrightarrow\quad
\mathsf P=\mathsf{NP}.
}
$$
This equivalence does not determine whether $A$ belongs to $\mathsf P$.
There is also an unconditional nonuniform upper bound:
$$
A\in\mathsf P/\mathsf{poly}.
$$
For inputs of length $N$, provide the advice list
$$
Q_1,Q_2,\ldots,Q_N.
$$
The bound $Q_\tau\le U_\tau$ shows that each entry needs $O(\log_2(\tau+1))$ bits, so the whole list has length $O(N\log_2(N+1))$.
After validating an input, compute $\tau$ and compare its budget with the advised value $Q_\tau$. This takes polynomial time. The missing ingredient for a uniform polynomial-time algorithm is computing the advice values uniformly.
The query characterization permits exact computation without enumerating all $2^{B_\tau}$ candidate families.
Let
$$
N_\tau=2^\tau-1,\qquad M_\tau=2^{N_\tau}.
$$
There are $N_\tau$ nonempty possible blocks and $M_\tau$ forbidden-block families.
A query history consists of forbidden families
$$
\mathcal F_1,\ldots,\mathcal F_\ell
$$
and their answers. Let $H$ denote the partitions consistent with this history.
Define a recursive predicate $E(H,d)$, meaning that $H$ can be identified with at most $d$ additional queries:
$$
H_1=\{\Pi\in H:\Pi\cap\mathcal F=\varnothing\},
\qquad H_0=H\setminus H_1.
$$
Return true if, for some $\mathcal F$, both $E(H_1,d-1)$ and $E(H_0,d-1)$ are true.
This recursion is correct by induction on $d$. A successful choice supplies the root query and successful strategies for both branches. Conversely, the root query of any successful strategy has a forbidden family included in the enumeration, and its two continuations must satisfy the recursive conditions.
There is no need to store $H$ explicitly. Enumerate all partitions and check them against the stored history. Partition enumeration uses polynomial space in $\tau$: for example, assign each type its block’s least element, giving an injective representation among $\tau^\tau$ strings. Thus
$$
B_\tau\le\tau^\tau.
$$
If $q\ge U_\tau$, answer yes immediately. Otherwise the recursive depth is at most $U_\tau$. At depth $d$, each forbidden family causes at most two calls of depth $d-1$. The work per call, apart from recursion, is bounded by
$$
2^{O(\tau\log_2(\tau+1))}
\operatorname{poly}(U_\tau).
$$
This includes partition enumeration, history checking, and enumeration overhead.
The resulting deterministic running-time bound is
$$
\boxed{
2^{O\!\left(2^\tau\,\tau\log_2(\tau+1)\right)}
+\operatorname{poly}(L).
}
$$
A depth-first implementation stores at most $U_\tau$ forbidden-family bit vectors, each of length $N_\tau$, together with loop counters and polynomial-size partition-enumeration state. Its space bound is
$$
\boxed{
O\!\left(2^\tau\,\tau\log_2(\tau+1)\right)
+\operatorname{poly}(L).
}
$$
These bounds prove uniform computability, but remain far from polynomial time.
The numerical masses cannot encode an instance-specific source of hardness in this model: arbitrary rational payoff rescaling removes them exactly. The unresolved problem is the uniform computation of the sequence $Q_\tau$.
The finite constructions prove that the Bell-number lower bound is attained for support sizes five and six. They do not establish its attainability for general support size, nor a polynomial-time algorithm for the threshold decision problem.
⟨structured verdict parsed — rendered above⟩
The output is a correct substantive partial solution, with one minor error in the running-time accounting. It establishes mass invariance, an exact characterization of realizable queries, general query bounds, the exact values $Q_5=6$ and $Q_6=8$, and the claimed conditional hardness equivalence. It does not settle the polynomial-time classification requested by USER_TASK, as the prover explicitly acknowledges.
Verified.
For every type, factor, and action profile, the rescaling
$$
u'_{t,f}=\frac{\mu_t}{\nu_t}u_{t,f}
$$
preserves that type’s mass-weighted payoff contribution. Consequently, the displayed equality holds for every coalition and every permitted deviation.
All relevant hypotheses are satisfied:
Transforming in both directions therefore proves $Q(\mu)=Q(\nu)$. The conclusion that the optimum depends only on the labeled support size is justified.
The polynomial-time rescaling claim is also valid: rational multiplication and division increase encoding lengths by polynomial amounts and do not require expanding the product of factor action spaces.
Verified.
Profitability of a fixed coalition depends only on its available actions, its members’ payoffs, and the default actions outside it. The partition of the outside types is irrelevant because they remain at the default profile.
Thus the oracle returns one exactly when none of the actual blocks belongs to $\mathcal F_G$. This uses the task’s strict-profitability convention correctly.
Verified, including singleton blocks.
For a coalition containing $r$, the stated gain simplifies correctly to
$$
\frac12-|B\setminus C|-|C\setminus B|.
$$
It equals $\frac12$ when $C=B$ and is at most $-\frac12$ otherwise. A coalition excluding $r$ cannot change the factor’s profile.
When $B=\{r\}$, the same calculation remains valid: the designated singleton is profitable, while every strict superset incurs a negative gain.
Combining factors preserves exactly the union of their profitable-coalition families. The argument uses both necessary properties of the model:
A positive total gain must contain a positive factor gain, and a coalition can realize a positive factor gain while retaining defaults in all other factors. There is therefore no interference between factors.
The empty-family construction is valid. The description-length and construction-time bounds are consistent with two profiles per factor and polynomial-size rational payoffs.
Verified.
For one factor, the number of coalition-action pairs is bounded by
$$
\prod_{t\in T}(1+|A_{t,f}|).
$$
For each type, the enumeration either excludes it from the coalition or includes it with one of its factor actions. Including its default action is permitted and necessary.
The bound by $(m+1)^\tau$ follows. Exact rational comparisons correctly distinguish positive gains from zero gains. Checking factors separately is justified by the same additive argument used above.
Verified.
The modified gain is
$$
\frac12-|B\setminus C|-|(C\cap S)\setminus B|.
$$
For coalitions containing $r$, this is positive exactly when $C\cap S=B$. Types outside $S$ contribute zero and therefore impose no additional restriction.
The construction realizes precisely the claimed tests on $\Pi|_S$, including cases where a restricted block extends outside $S$.
Verified.
A deterministic binary-answer strategy of worst-case depth at most $q$ has at most $2^q$ leaves, even when it stops early on some paths. Exact identification requires distinct leaves for the $B_\tau$ partitions. Hence
$$
Q_\tau\ge\lceil\log_2 B_\tau\rceil.
$$
Verified.
Only coalitions containing $i$ can toggle. Their gain is positive exactly when they also contain $j$. Thus the oracle returns zero exactly when the two types share a block.
Testing all pairs determines the partition and proves the stated upper bound.
Verified.
Representatives of different blocks of the identified restriction belong to different actual blocks. Therefore type $i$ can share a block with at most one representative.
Combining the pair factors for a selected code bit produces a negative oracle answer exactly when the correct representative’s code has that bit set. If type $i$ shares no block with an earlier type, every answer corresponds to the zero code.
The coding argument and induction establish $U_\tau$. For $\tau=1$, the sum is empty and gives the correct zero-query bound.
The polynomial-time implementation claim is justified by the polynomial number of queries and the polynomial description size of each insertion query.
Verified by independent exhaustive recomputation.
I recomputed the bitwise-OR signatures of all partitions from the supplied block-code table. The checks confirm:
The negated oracle answers recover the signature bits. Consequently, six nonadaptive queries identify the partition. Together with
$$
32<52\le64,
$$
this proves $Q_5=6$.
Verified.
For each of the eleven specified partitions, toggling the least significant signature bit produces an unused signature. Independent enumeration confirms that each corresponding five-bit prefix occurs for exactly one partition.
Those eleven partitions are exactly the partitions with at least four blocks. The claimed adaptive stopping rule is therefore valid.
Verified.
Restriction tests allow the first stage to identify the partition induced on the first five types, regardless of where type $6$ belongs.
The two query-count cases are correct:
The Bell-number recurrence is correctly justified, and the listed values yield $B_6=203$. Thus the information lower bound matches the eight-query strategy.
The claim of at most $26$ factors per query is valid and conservative. The signature-bit queries actually use at most twelve factors.
Verified.
The reduction handles valid instances with large budgets using the pair-test upper bound, and rejects malformed instances separately. For the remaining instances, mass invariance preserves membership.
The explicit support list ensures $\tau\le L$, so the unary support-size encoding has polynomial length. Canonical binary budget encodings give at most $h_\tau$ relevant strings for each support size. The cumulative sparsity bound $O(N^3)$ is valid.
The stated version of Mahaney’s theorem is correct: it applies to sparse languages that are $\mathsf{NP}$-hard under polynomial-time many-one reductions, without requiring membership in $\mathsf{NP}$. This is explicitly the formulation in [Grochow’s Theorem 2.1](https://arxiv.org/html/1610.05825v1).
All hypotheses are satisfied after composing the reductions. Hence the implication from hardness of $A$ to $\mathsf P=\mathsf{NP}$ follows.
Verified.
The fixed instances have the claimed answers:
Mapping syntactically valid but out-of-range budgets to the fixed no-instance correctly respects the definition of $S$.
The constructed masses are positive dyadic rationals, normalize exactly, and have polynomial total encoding length. No unintended interpretation of “binary-rational” is needed.
The reductions therefore establish polynomial-time many-one equivalence of $A$ and $S$.
Verified.
Under $\mathsf P=\mathsf{NP}$, the proposed satisfiability reduction can decide its input and select the fixed yes-instance or no-instance in polynomial time. Combined with the preceding implication, this proves the displayed equivalence.
This establishes neither an unconditional hardness result nor membership of $A$ in $\mathsf P$. The prover states that limitation accurately.
Verified.
Each advice value $Q_\tau$ has logarithmic encoding length under the established upper bound. The full advice list is polynomial in input length, and validation followed by a budget comparison is polynomial-time.
The distinction between nonuniform advice and uniform computation is correctly maintained.
Verified.
The base cases are appropriate, including empty consistent sets. The recursive characterization follows directly from the exhaustive characterization of available queries.
Non-splitting queries cause no termination problem because the remaining depth decreases. The preliminary upper-bound check ensures bounded recursion depth even when the supplied budget is very large.
The partition representation and history-based consistency checking suffice for finite enumeration without storing every partition.
The following statement is false as written:
“The work per call, apart from recursion, is bounded by”
followed by
$$
2^{O(\tau\log_2(\tau+1))}\operatorname{poly}(U_\tau),
$$
and the assertion that this includes enumeration overhead.
An invocation can enumerate all
$$
M_\tau=2^{2^\tau-1}
$$
forbidden families. That enumeration alone exceeds the claimed per-call bound. For example, with the full partition universe and one remaining query, when there are more than two partitions no candidate can succeed, so the invocation exhausts the family enumeration.
Severity: minor. This is a bookkeeping error in an intermediate estimate. The final displayed running-time bound already accommodates the forbidden-family branching, and the space bound is consistent with the described depth-first implementation.
Minimum clarification required: State precisely whether the smaller work estimate applies per candidate family or per recursive invocation, and explicitly account for the family-enumeration loop in the running-time justification.
No additional mathematical construction is required.
The output engages the target and proves substantial structural results. Its final unresolved point is nevertheless exactly the central question in USER_TASK: whether the threshold decision problem has a uniform polynomial-time algorithm or an unconditional hardness classification.
Severity: major as an incompleteness of the assigned task, not as a false proof claim. The prover explicitly labels its solution partial.
To complete the assignment, the prover would need a rigorous classification addressing that remaining question. Neither the finite exact cases, the advice bound, nor the conditional hardness equivalence supplies such a classification.
⟨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.