Answer: \(\mathrm{NP}\)-hard under polynomial-time Turing reductions, already for \(p=1\) and \(\tau=O(n^2)\). A learner with the stated polynomial query and computation bounds would imply \(\mathrm{P}=\mathrm{NP}\).
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLEARN-CP-NET is resolute—i.e., it is guar- anteed to output a consistent CP-net N—and runs in time polynomial in np and q in the worst case.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given oracle access to exact rational fractions of a society preferring each response to any queried pair of outcomes, where the society is an unknown distribution with support size \(\tau\) over acyclic binary CP-nets with at most \(p\) parents per node, can an adaptive learner output a rational distribution over CP-net types that matches the oracle on every outcome pair using polynomially many queries and computation in \(n^p\), \(\tau\), and response-mass bit length \(L\)?
Let \(m=n\geq 1\) be the number of known binary variables, with outcomes \(\{0,1\}^n\), and let \(0\leq p\leq n-1\). Types are acyclic CP-nets with at most \(p\) parents per node and complete CPTs specifying strict binary preferences.
For distinct outcomes \(a,b\), a node witnesses \(a\) over \(b\) when their assignments agree on all its ancestors and its CPT prefers its value in \(a\). A type responds \(a\succ b\) if a forward witness exists and no reverse witness exists, responds \(b\succ a\) symmetrically, and otherwise responds “undetermined.”
A society is encoded by its support: the list of its \(\tau\) distinct types with positive binary-rational masses summing to \(1\); \(\tau\) counts supported types, not possible types. In this learning problem that list is hidden: the learner receives \(n,p,\tau,L\) and oracle access only.
Each query specifies any distinct outcome pair and returns the exact masses of all three responses. Here \(L\) bounds the binary encoding length of each returned rational; oracle evaluation costs one query, with reading and processing charged normally.
The required output is an explicit finite list of types from the same class and positive binary-rational masses summing to \(1\), reproducing all three response masses on every distinct outcome pair. Its support need not equal the hidden support or have size \(\tau\).
Is this exact reconstruction problem solvable by an adaptive learner using polynomially many queries and polynomial computation in \(n,n^p,\tau,L\), or is it NP-hard in this oracle model?
Known for a single user: LEARN-CP-NET outputs a consistent CP-net in time polynomial in \(n^p\) and its confidence threshold \(q\), without guaranteeing agreement on every outcome pair. [Guerin–Allen–Goldsmith](https://www.cs.uky.edu/~goldsmit/papers/Guerin_LearnCPnet_ADT.pdf)
Exact membership-query learning algorithms are also known for individual complete bounded-parent acyclic binary CP-nets using swap comparisons. [Alanazi–Mouhoub–Zilles](https://arxiv.org/pdf/1801.03968)
No result settling reconstruction of arbitrary rational societies under the response oracle defined above was located.
Exact reconstruction is \(\mathrm{NP}\)-hard in the following precise sense: a learner with the stated polynomial query and computation bounds would yield a polynomial-time algorithm for an \(\mathrm{NP}\)-hard decision problem.
This holds already for \(p=1\), with \(\tau=O(n^2)\). The proof allows the learner to output arbitrary types and an arbitrary support size.
I first give the proof for rationals encoded by binary numerators and denominators. Section 6 extends it to the stricter interpretation in which all masses must be dyadic.
For \(r\geq 1\), define the correlation polytope
\[ \operatorname{COR}(r) = \operatorname{conv}\{vv^{\mathsf T}:v\in\{0,1\}^r\}. \]
Equivalently, a rational symmetric matrix \(M\) belongs to \(\operatorname{COR}(r)\) exactly when there is a distribution on \(V\in\{0,1\}^r\) satisfying
\[ \mathbb E[V_i]=M_{ii}, \qquad \mathbb E[V_iV_j]=M_{ij}. \]
Exact rational membership in this polytope is \(\mathrm{NP}\)-hard under polynomial-time Turing reductions. This is the correlation-polytope membership theorem of [Pitowsky, *Correlation polytopes: Their geometry and complexity*](https://link.springer.com/article/10.1007/BF01594946).
Write \(q_i=M_{ii}\) and \(q_{ij}=M_{ij}\), including \(q_{ii}=q_i\). We can immediately reject matrices violating symmetry or any of the necessary conditions
\[ 0\leq q_i\leq 1, \qquad \max(0,q_i+q_j-1)\leq q_{ij}\leq \min(q_i,q_j). \]
For a matrix passing these checks, define the following binary joint-probability tables:
| \((s,t)\) | \(C_{ij}(s,t)\) |
|---|---|
| \((1,1)\) | \(q_{ij}\) |
| \((1,0)\) | \(q_i-q_{ij}\) |
| \((0,1)\) | \(q_j-q_{ij}\) |
| \((0,0)\) | \(1-q_i-q_j+q_{ij}\) |
Each table is nonnegative and sums to \(1\). For \(i=j\), it assigns mass only to equal bits.
These local tables exist even when no joint distribution realizing the entire matrix exists.
Use \(n=2r\) variables, denoted
\[ A_1,\ldots,A_r,\quad B_1,\ldots,B_r. \]
For every \(v\in\{0,1\}^r\), construct a type \(N_v\) with two disjoint directed chains:
\[ A_1\longrightarrow\cdots\longrightarrow A_r, \qquad B_1\longrightarrow\cdots\longrightarrow B_r. \]
The root nodes prefer the bit \(v_1\). At either node indexed by \(i>1\), when its parent has value \(c\), its preferred bit is
\[ v_i\oplus c. \]
Thus \(N_v\) is acyclic, has at most one parent per node, and has complete strict binary CPTs. Every listed parent genuinely changes the child’s preference.
Consider any distinct outcomes \(a,b\). In each chain on which they differ, let \(i\) be the first differing index.
Exactly that node can witness a preference:
For the first differing node \(A_i\), define
\[ s= \begin{cases} a_{A_1},&i=1,\\ a_{A_i}\oplus a_{A_{i-1}},&i>1. \end{cases} \]
The parent value in the second case is common to \(a,b\). This witness favors \(a\) exactly when \(v_i=s\). Define \(t\) analogously for the first differing node \(B_j\).
Consequently, we can simulate an oracle \(O_M\) for every query as follows.
Only one chain differs. If its witness corresponds to \(v_i=s\), return
\[ \Pr(a\succ b)= \begin{cases} q_i,&s=1,\\ 1-q_i,&s=0, \end{cases} \]
with the remaining mass assigned to \(b\succ a\), and zero undetermined mass.
Both chains differ. Return
\[ \Pr(a\succ b)=C_{ij}(s,t), \]
\[ \Pr(b\succ a)=C_{ij}(1-s,1-t), \]
\[ \Pr(\text{undetermined}) = 1-C_{ij}(s,t)-C_{ij}(1-s,1-t). \]
These are valid probability triples: the two determined responses correspond to disjoint entries of a joint table.
The simulator scans the outcomes and performs a constant number of rational operations. Its running time and answer lengths are polynomial in the encoding length of \(M\). In particular, we can supply a polynomially bounded \(L\).
If \(M\in\operatorname{COR}(r)\), any distribution realizing its moments, transferred from \(v\) to \(N_v\), realizes every answer of \(O_M\). The simulator therefore does not need to know a realizing distribution.
This is the essential step: the learner need not return the two-chain types.
Fix two distinct nodes \(X,Y\) in any allowed type. For each \((s,t)\in\{0,1\}^2\), compare the outcomes having
\[ a_X=s,\quad a_Y=t,\qquad b_X=1-s,\quad b_Y=1-t, \]
with every other variable equal to zero in both outcomes.
Let \(U^{st}\) indicate an undetermined response.
If one node is an ancestor of the other, only the ancestral node can witness. Its strict binary preference makes the response determined in all four comparisons. Hence
\[ \sum_{s,t}U^{st}=0. \]
If neither node is an ancestor of the other, both can witness. Their preferred bits are fixed across these four comparisons: neither CPT depends on the other node, and all remaining variables are fixed.
Exactly two comparisons make the witnesses favor opposite outcomes. Therefore
\[ \sum_{s,t}U^{st}=2. \]
For a society, linearity gives
\[ \sum_{s,t}\Pr(\text{undetermined in comparison }(s,t)) = 2\Pr(X,Y\text{ are incomparable by ancestry}). \tag{1} \]
This identity holds for arbitrary supported graphs and CPTs.
For \(O_M\), apply these four comparisons to \(A_i,B_j\). Their transformed bits are simply \(s,t\), because all their other variables are zero. The simulator therefore gives
\[ \sum_{s,t}\Pr(\text{undetermined}) = 4-\sum_{s,t}C_{ij}(s,t) -\sum_{s,t}C_{ij}(1-s,1-t) = 2. \]
Suppose a reconstruction consists of types \(T_h\) with positive masses \(w_h\). By (1), every supported \(T_h\) must make \(A_i,B_j\) incomparable by ancestry.
This holds for every \(i,j\). Positivity is important: an average incomparability probability equal to \(1\) forces incomparability in every supported type.
For each output type \(T_h\), let
\[ \alpha_i^{(h)} = \text{the preferred bit of }A_i\text{ in the all-zero parent context}, \]
and define \(\beta_i^{(h)}\) similarly for \(B_i\).
Swap queries in the all-zero context imply
\[ \sum_h w_h\alpha_i^{(h)}=q_i, \qquad \sum_h w_h\beta_i^{(h)}=q_i. \tag{2} \]
Now compare outcomes differing only on \(A_i,B_j\), with both values equal to \(1\) in \(a\) and \(0\) in \(b\).
These nodes are incomparable in every output type. Both therefore witness, and the forward response occurs exactly when both preferred bits are \(1\). Agreement with \(O_M\) yields
\[ \sum_h w_h\alpha_i^{(h)}\beta_j^{(h)}=q_{ij}. \tag{3} \]
Taking \(j=i\), equations (2)–(3) give
\[ \sum_h w_h \bigl(\alpha_i^{(h)}-\beta_i^{(h)}\bigr)^2 = q_i+q_i-2q_{ii} = 0. \]
Every summand is nonnegative and every mass is positive. Thus
\[ \alpha_i^{(h)}=\beta_i^{(h)} \quad\text{for every }i,h. \]
Set \(v_i^{(h)}=\alpha_i^{(h)}\). Equation (3) becomes
\[ M=\sum_h w_hv^{(h)}(v^{(h)})^{\mathsf T}. \tag{4} \]
Hence any valid reconstruction of \(O_M\) produces a convex decomposition certifying \(M\in\operatorname{COR}(r)\).
Let
\[ d=\frac{r(r+1)}2, \]
the number of distinct matrix coordinates.
If a rational \(M\) belongs to \(\operatorname{COR}(r)\), Carathéodory’s theorem gives a representation using at most \(d+1\) vertices. We may take those vertices to be affinely independent and discard zero coefficients.
The remaining coefficients are rational. Indeed, after appending a normalization coordinate, their values solve a full-column-rank linear system with integer coefficients and rational right-hand side. An invertible square subsystem determines them by Cramer’s rule.
We therefore obtain \(k\) distinct vectors and positive rational weights, for some
\[ 1\leq k\leq d+1. \]
The types \(N_v\) are distinct for distinct \(v\), so this is a promised society with exact support count \(\tau=k\).
The reduction does not know \(k\), but can try every value in this polynomial-size range.
Assume an exact reconstruction learner exists with polynomial bounds on both computation and queries on every promised input.
Given \(M\), perform the necessary checks in Section 1. For each \(k=1,\ldots,d+1\):
All simulations and checks take polynomial time. Since \(p=1\), the parameter \(n^p\) is just \(n\).
If \(M\in\operatorname{COR}(r)\): at least one tried support count is correct by Section 4. That run receives a fully promised input. Its reconstruction passes the verification by Section 3.
If \(M\notin\operatorname{COR}(r)\): no output can pass verification, because (4) itself certifies membership.
The latter argument does not assume any behavior of the learner outside its promise. Such runs are explicitly capped, and their outputs are independently verified.
Thus the proposed learner would decide correlation-polytope membership in polynomial time. This proves the claimed hardness.
In particular, the obstruction survives despite an efficiently evaluable oracle and polynomial hidden support; it is not an argument based merely on exponentially many possible types.
If “binary-rational” means exclusively a rational with power-of-two denominator, Section 4 alone is insufficient: a rational convex decomposition need not have dyadic weights. The following refinement closes that gap.
Identify symmetric matrices with their \(d\) coordinates. Write \(\phi(v)\) for the resulting vertex vector.
Consider the following \(d+1\) vertices:
\[ b_0=\phi(0),\qquad b_i=\phi(e_i),\qquad b_{ij}=\phi(e_i+e_j)\quad(i<j). \]
They are affinely independent. More strongly, their augmented coordinate matrix is unimodular: the pair-coordinate rows identify the \(b_{ij}\) coefficients, the singleton rows then identify the \(b_i\) coefficients, and normalization identifies the \(b_0\) coefficient.
Choose a power of two \(S>d\). Give each nonzero listed vertex weight \(1/S\), and give \(b_0\) weight \(1-d/S\). Their convex combination \(c\) is dyadic and lies in the interior of their full-dimensional simplex, hence in the interior of \(\operatorname{COR}(r)\).
Every baseline weight is at least \(1/S\).
Every facet inequality can be written
\[ a\cdot x\leq b \]
with integer coefficients satisfying \(\lvert a_\ell\rvert,\lvert b\rvert\leq H\), where we can take \(H=(d+1)!\).
To justify this bound, choose \(d\) affinely independent binary vertices on the facet. Cofactors of their augmented coordinate matrix give an integer normal and constant; the relevant determinants have magnitude at most \(d!\).
Because \(c\) is strictly interior and has denominator \(S\), every such facet has slack at least \(1/S\) at \(c\).
Let \(Q\) be the product of the denominators of the input coordinates. Its binary length is at most the input length. If the input point \(q\) is outside the polytope, it violates some integer facet by at least \(1/Q\).
Choose a positive dyadic \(\varepsilon\) satisfying
\[ \varepsilon dH\leq \frac1{4Q}, \]
and form
\[ z=(1-\varepsilon)q+\varepsilon c. \]
Round each coordinate of \(z\) to a dyadic number, obtaining \(x\), with coordinate error at most
\[ \delta=\frac{\varepsilon}{4SdH}. \]
All required binary precisions are polynomial in the input length and \(d\).
If \(q\) is inside, every facet has slack at least \(\varepsilon/S\) at \(z\). Rounding changes a facet value by at most \(dH\delta=\varepsilon/(4S)\). Thus \(x\) is strictly inside, with slack at least \(\varepsilon/(2S)\).
If \(q\) is outside, a violated facet remains violated: moving to \(z\) changes its value by at most \(\varepsilon dH\), and rounding changes it by at most \(\varepsilon/(4S)\). Together these changes are strictly smaller than its original violation \(1/Q\).
Consequently,
\[ q\in\operatorname{COR}(r) \quad\Longleftrightarrow\quad x\in\operatorname{COR}(r), \]
and every yes-instance becomes a dyadic interior point with a polynomially bounded positive facet slack.
Let \(\lambda>0\) be the slack bound just obtained. Choose a positive dyadic \(\eta\leq 1/2\) with
\[ \eta\leq \frac{\lambda}{4dH}. \]
Then
\[ y=\frac{x-\eta c}{1-\eta} \]
still lies in the polytope. Indeed,
\[ y-x=\frac{\eta}{1-\eta}(x-c), \]
so each facet value changes by at most \(2\eta dH\leq\lambda/2\).
By Carathéodory’s theorem, write
\[ y=\sum_{k=1}^{\ell}\gamma_k u_k, \qquad \ell\leq d+1. \]
Thus \(x=\eta c+\sum_k\theta_k u_k\), where \(\theta_k=(1-\eta)\gamma_k\).
Round each \(\theta_k\) downward to a multiple of a sufficiently small dyadic grid \(g\), obtaining \(\widetilde\theta_k\). The deficit in every moment coordinate and in total mass is at most \((d+1)g\).
Denote these deficits by \(\Delta_i,\Delta_{ij},\Delta_0\). They are dyadic. Correct the weights of the baseline vertices by
\[ t_{ij}=\Delta_{ij}, \qquad t_i=\Delta_i-\sum_{j\neq i}\Delta_{ij}, \]
\[ t_0=\Delta_0-\sum_i\Delta_i+\sum_{i<j}\Delta_{ij}. \]
These formulas correct every moment and total mass exactly. Every correction has magnitude at most \((d+1)^2g\).
Choose
\[ g\leq \frac{\eta}{2S(d+1)^2}. \]
Each original baseline weight is at least \(\eta/S\), so every corrected baseline weight remains positive. The other weights are nonnegative; discard zeros and merge repeated vertices.
This gives an exact positive dyadic decomposition of \(x\) using at most \(2d+2\) distinct vertices. The required dyadic precision is polynomially bounded. This is an existence argument; finding the decomposition is precisely the reconstruction difficulty.
For the dyadic interpretation, first transform the source instance to \(x\), then use Sections 2–5 with support-count guesses \(1,\ldots,2d+2\). If \(x\) violates the preliminary probability bounds, reject immediately. Yes-instances pass those bounds and have a promised dyadic society. Verification certifies \(x\in\operatorname{COR}(r)\), which is equivalent to membership of the original instance.
Thus the hardness result holds under either interpretation of “binary-rational.”
For comparison, \(p=0\) admits exact reconstruction in \(O(n\tau)\) queries.
Each type is identified by its preferred-bit vector \(v\). For any nonempty coordinate set \(D\), choose outcomes differing exactly on \(D\), with \(a_D=s\). Every differing node witnesses, so
\[ \Pr(a\succ b)=\Pr(V_D=s). \]
The oracle therefore supplies arbitrary cylinder probabilities.
Explore prefixes of \(v\), retaining only positive-mass prefixes. Query one child’s mass and obtain the other by subtracting it from the parent mass. At each depth there are at most \(\tau\) positive prefixes, since each contains a supported vector.
After \(n\) levels this recovers all supported vectors and their exact masses. Arithmetic and output size are polynomial in \(n,\tau,L\).
The general reconstruction problem becomes hard already when one parent per node is permitted.
⟨structured verdict parsed — rendered above⟩
The argument resolves the assigned problem. It establishes hardness under polynomial-time Turing reductions, already for \(p=1\) and \(\tau=O(n^2)\), including when masses must be dyadic. I found no major or minor mathematical issues.
The conclusion concerns the combined requirement of polynomially many queries and polynomial computation. It does not separately establish a query lower bound.
The source problem is exact membership of a rational symmetric matrix in \(\operatorname{COR}(r)\). The stated hardness theorem applies to this problem; the cited paper explicitly identifies correlation-polytope membership as NP-complete. The matrix formulation used here is also explicitly identified with that polytope in the literature. [Pitowsky’s paper](https://link.springer.com/article/10.1007/BF01594946), [matrix membership formulation](https://optimization-online.org/wp-content/uploads/2017/08/6168.pdf).
The preliminary conditions are necessary for binary first and second moments. They make every entry of \(C_{ij}\) nonnegative, and the four entries sum to \(1\). For \(i=j\), substituting \(q_{ii}=q_i\) indeed makes both off-diagonal entries zero.
The distinction between locally valid tables and a globally realizable joint distribution is maintained throughout. No global consistency is assumed on a no-instance.
Each \(N_v\) satisfies the required type restrictions: its graph is acyclic, each node has at most one parent, and every parent context has a strict binary preference. Distinct vectors give distinct types.
On a chain where the outcomes differ, the first differing node has equal ancestor assignments. Every later differing node has an ancestor whose assignments differ, so it cannot witness. Thus there is exactly one witness from each differing chain.
The transformed bit correctly accounts for the conditional preference \(v_i\oplus c\), because the parent assignment is common at the first differing node.
When both chains differ, the two witnesses favor \(a\) precisely on the table entry \(C_{ij}(s,t)\), and both favor \(b\) on \(C_{ij}(1-s,1-t)\). Those entries are distinct, including when \(i=j\), so the stated undetermined mass is nonnegative.
Every answer requires only scanning the outcomes and a constant number of rational operations. Answer lengths are polynomially bounded by the source encoding. On a yes-instance, transferring a realizing distribution to the types \(N_v\) reproduces the entire oracle, not merely selected queries.
The four-comparison test in Section 3.1 is valid for arbitrary allowed output types.
If one of the two changed nodes is an ancestor of the other, the descendant cannot witness. The ancestral node can witness, because every other variable is unchanged. Strict binary preferences therefore give a determined response in all four comparisons.
If the nodes are incomparable, both can witness. Neither can be a parent of the other, and all remaining variables are fixed, so each preferred bit stays fixed across the four comparisons. Exactly two comparisons make the witnesses oppose one another.
Consequently, equation (1) correctly identifies the incomparability probability from oracle answers.
For each cross-block pair \(A_i,B_j\), the simulated oracle makes the sum of the four undetermined masses equal to \(2\). Equation (1) therefore forces incomparability probability \(1\).
Positive output weights imply that every supported type has this incomparability property for every cross-block pair. This correctly handles the learner’s freedom to output unrelated graphs and an arbitrary support size.
The all-zero-context swap queries establish equation (2). The comparisons changing only \(A_i,B_j\), from zeros to ones, establish equation (3): both changed nodes witness, their parent contexts are zero, and the forward response occurs exactly when both preferred bits equal \(1\).
Taking \(j=i\), the squared-difference calculation is correct. Binary values satisfy \(\alpha_i^2=\alpha_i\) and \(\beta_i^2=\beta_i\). Since the weighted sum of nonnegative squares is zero and every weight is positive, \(\alpha_i^{(h)}=\beta_i^{(h)}\) holds for every supported type.
Equation (4) follows. Thus any valid reconstruction yields a genuine correlation-polytope membership certificate.
Carathéodory’s theorem applies in the \(d=r(r+1)/2\) coordinate space and gives at most \(d+1\) vertices. Choosing an affinely independent representation makes the weights uniquely determined by an integer-coefficient linear system with rational right-hand side; hence they are rational.
After discarding zero weights, the resulting society has an exact positive support count in the guessed range. The reduction does not need to find that representation.
Trying every support count and capping each run correctly handles inputs outside the learner’s promise. On a yes-instance, at least one run is promised and succeeds. On a no-instance, equation (4) cannot pass verification, regardless of what an unpromised run returns.
The verifier does not need to check agreement on every outcome pair: the independently checked convex decomposition already suffices to reject every source no-instance. Polynomial computation also bounds the explicit output length, so parsing and exact verification remain polynomial.
Baseline simplex. The listed \(d+1\) vertices are affinely independent. The described coordinate elimination verifies unimodularity of their augmented matrix. All baseline weights are positive because \(S>d\), and each is at least \(1/S\). Thus \(c\) is a dyadic interior point.
Facet bounds. A facet contains \(d\) affinely independent vertices. Cofactors of their augmented binary coordinate matrix produce an integer facet equation, with determinant magnitudes bounded by \(d!\). The larger bound \(H=(d+1)!\) is therefore valid.
Strict interiority and denominator \(S\) give facet slack at least \(1/S\) at \(c\). Likewise, a violated integer facet at a rational input has violation at least \(1/Q\).
Membership-preserving perturbation. The preliminary checks from Section 1 ensure that the original coordinates lie in \([0,1]\). This supplies the coordinate bound needed for the estimate \(\varepsilon dH\) on movement toward \(c\).
For a source yes-instance, every facet has slack at least \(\varepsilon/S\) before rounding. The rounding error contributes at most \(\varepsilon/(4S)\), so the stated lower bound \(\varepsilon/(2S)\) is valid.
For a source no-instance, movement and rounding together are smaller than the original violation \(1/Q\). Indeed, \(SdH\geq1\) ensures \(\varepsilon/(4S)\leq\varepsilon dH\), and the combined bound is at most \(1/(2Q)\).
The required precision is polynomial: \(\log H\), \(\log S\), and \(\log Q\) are polynomially bounded.
Small dyadic decomposition. For a transformed yes-instance, \(x\) and \(c\) lie in the unit cube. The estimate \(2\eta dH\leq\lambda/2\) therefore correctly keeps \(y\) inside the polytope.
Rounding the at most \(d+1\) auxiliary weights downward gives deficits bounded by \((d+1)g\). The written correction formulas restore every singleton moment, pair moment, and total mass exactly.
The correction bound \((d+1)^2g\) is valid, including for \(t_0\), whose formula has \(d+1\) terms. The chosen grid makes every negative correction smaller than half the minimum baseline weight. All corrected baseline weights remain positive.
The deficits are dyadic because \(x\), the baseline contribution, and the rounded contribution are dyadic; the unrounded auxiliary weights need not be dyadic. Discarding zeros and merging repetitions gives at most \(2d+2\) distinct vertices.
Thus the transformed yes-instances have promised dyadic societies with polynomial support. The dyadic reduction is complete.
For \(p=0\), every changed coordinate witnesses. A forward response occurs exactly when the preferred-bit vector matches the specified assignment on all changed coordinates. The oracle therefore returns the claimed cylinder probabilities.
Prefix exploration retains at most \(\tau\) positive prefixes at every depth, giving \(O(n\tau)\) queries. Subtraction supplies the other child’s mass, and at depth \(n\) the positive leaves give the exact society.
This includes \(n=1\). The hardness construction uses \(n=2r\geq2\), so \(p=1\leq n-1\) is always admissible. The dyadic bounds also remain valid when \(r=d=1\).
No repair is required. The substantive progress is the complete oracle reduction, especially the extraction argument that accommodates arbitrary reconstructed types and the dyadic extension that preserves the promise.
⟨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.