Answer: \(\mathrm{NP}\)-complete, even with binary domains, unit importance weights, exact-match similarities, catalogue equal to support, and dyadic masses.
Theorem 4 — class: other
Given a shared catalogue \(C\), attributes \(A\) with finite value sets, the paper’s similarity rule, and a finite set \(T\) of complete preference profiles with rational masses \(\mu_t\), find an adaptive question tree minimizing \(\sum_{t\in T}\mu_t\ell(t)\), where \(\ell(t)\) is the number of questions asked to type \(t\). Require that at every leaf, for every positive-mass type consistent with that path, the retrieval set for the partial query equals the retrieval set for that type’s complete query; equivalently, require Theorem 4’s safe-stopping test for each such type.
Given a nonempty catalogue \(C\) of \(n\) distinct products, each described on \(m\geq1\) attributes \(A\), let each attribute \(a\) have an explicitly listed nonempty finite domain \(D_a\).
Input includes positive binary-rational importance weights \(w_a\) and explicit binary-rational similarity tables \(s_a:D_a\times D_a\to[0,1]\), with \(s_a(x,y)=1\) exactly when \(x=y\); no triangle inequality is required.
For a partial query \(q\) specifying attributes \(S\subseteq A\), define \(\operatorname{Sim}(c,q)=\frac{\sum_{a\in S}w_as_a(c_a,q_a)}{\sum_{a\in A}w_a}\) and \(R(q)=\operatorname*{arg\,max}_{c\in C}\operatorname{Sim}(c,q)\), retaining every tie; thus \(R(\varnothing)=C\).
A society is given by its support: the list of the \(\tau\) distinct complete types \(t\in T\subseteq\prod_{a\in A}D_a\) with positive masses \(\mu_t\), each a binary rational, with \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
A deterministic adaptive question tree starts with the empty query, asks one previously unasked attribute at each internal node at unit cost, and branches on its reported value; every supported type must reach a leaf.
A leaf with path query \(q\) is legal precisely when \(R(q)=R(t)\) for every supported type agreeing with \(q\); no requirement is imposed on unsupported completions. Let \(\ell(t)\) be the depth reached by \(t\).
Given also a binary-rational bound \(B\geq0\), decide whether a legal tree satisfies \(\sum_{t\in T}\mu_t\ell(t)\leq B\). Let \(L\) be the total input bit length; state running times in \(m,\tau,n,\sum_{a\in A}|D_a|,L\).
Is this decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
For finite catalogues, a necessary-and-sufficient characterization of safe stopping under every possible completion is known, without a complexity classification for optimal adaptive trees ([McSherry, 2003](https://www.ijcai.org/Proceedings/03/Papers/017.pdf)).
Minimizing expected tests for unique-object identification by binary decision trees is \(\mathrm{NP}\)-complete, a different stopping problem ([Hyafil–Rivest, 1976](https://people.csail.mit.edu/rivest/pubs/HR76.pdf)); no result settling the exact mass-weighted retrieval problem above was located.
The decision problem is \(\mathrm{NP}\)-complete. Hardness already holds when every domain is \(\{0,1\}\), all importance weights are \(1\), similarities are exact-match similarities, and the catalogue equals the society’s support.
The essential observation is that, on this restricted family, the stated retrieval stopping rule is exactly unique-object identification. The proof below also handles the interpretation of “binary-rational” as requiring dyadic rationals.
Suppose \(C=T\), all weights equal \(1\), and each similarity table satisfies \(s_a(x,y)=1\) for \(x=y\) and \(s_a(x,y)=0\) otherwise.
For a partial query \(q\) on attributes \(S\), define its consistent support by
\[ T_q=\{t\in T:t_a=q_a\text{ for every }a\in S\}. \]
Consider any query with \(T_q\ne\varnothing\). Every product in \(T_q\) matches all specified attributes and therefore has similarity \(|S|/m\). Every product outside \(T_q\) mismatches at least one specified attribute and therefore has strictly smaller similarity. Consequently,
\[ R(q)=T_q. \]
For a complete supported type \(t\), distinctness of the products gives \(R(t)=\{t\}\). Hence a supported leaf is legal precisely when
\[ T_q=\{t\}\quad\text{for every }t\in T_q, \]
which is equivalent to \(|T_q|=1\).
Thus legal retrieval trees on this family are precisely trees identifying every supported type. This conclusion uses the actual partial-query retrieval set, including all ties.
Hyafil and Rivest prove that the following problem is \(\mathrm{NP}\)-complete: given finitely many objects, explicitly specified binary tests, and an integer \(K\), decide whether an identification tree has total external path length at most \(K\). If \(\ell_i\) is the depth of object \(i\), that objective is \(\sum_i\ell_i\). See [Hyafil–Rivest, 1976](https://people.csail.mit.edu/rivest/pubs/HR76.pdf).
We may restrict to instances with \(N\geq2\) objects, \(m\geq1\) tests, and distinct test-outcome vectors. Indeed, indistinguishable objects make identification impossible, and detecting duplicate vectors is polynomial-time. Such instances can be mapped to a fixed no-instance; the remaining trivial cases can likewise be decided directly.
We may also require that no test repeats along a path. A repeated test has an outcome already determined by an earlier answer. Replacing its node by the determined child preserves identification and decreases depths. Repeating this operation yields a tree of depth at most \(m\).
For each source object \(i\), let \(t^{(i)}\in\{0,1\}^m\) be its test-outcome vector. Construct the retrieval instance with:
The vectors are distinct, so the constructed catalogue and support satisfy the input requirements. By Section 1, legal retrieval trees and source identification trees correspond, with identical object depths.
If arbitrary rationals encoded by binary numerators and denominators are allowed, set \(\mu_i=1/N\) and \(B=K/N\). Then the threshold correspondence is immediate:
\[ \sum_i\mu_i\ell_i\leq B \quad\Longleftrightarrow\quad \sum_i\ell_i\leq K. \]
For completeness, the following construction establishes hardness even when every mass and the bound must be dyadic.
Choose a power of two \(P\) satisfying \(P\geq N(Nm+1)\), and write
\[ P=Nh+r,\qquad h=\lfloor P/N\rfloor,\qquad 0\leq r<N. \]
In particular, \(h\geq Nm+1>rm\). Assign masses
\[ \mu_i=h/P\quad(i<N),\qquad \mu_N=(h+r)/P, \]
and set \(B=(hK+rm)/P\).
These masses are positive dyadic rationals and sum to \(1\). For any corresponding tree, write \(E=\sum_i\ell_i\). Its expected retrieval cost is
\[ \sum_i\mu_i\ell_i=\frac{hE+r\ell_N}{P}. \]
If the source is a yes-instance, take an identification tree without repeated tests. It has \(E\leq K\) and \(\ell_N\leq m\), so its retrieval cost is at most \((hK+rm)/P=B\).
Conversely, suppose a legal retrieval tree has cost at most \(B\). Section 1 makes it an identification tree. If \(E>K\), integrality gives \(E\geq K+1\). Since \(\ell_N\geq0\),
\[ hE+r\ell_N\geq h(K+1)>hK+rm, \]
contradicting the cost bound. Therefore \(E\leq K\).
Taking the least sufficiently large power of two gives \(\log P=O(\log N+\log m)\). The construction copies the explicit outcome matrix and performs polynomial-time integer arithmetic. Its output length and running time are polynomial in the source input length. In the resulting instance, \(n=\tau=N\) and \(\sum_a|D_a|=2m\).
This proves \(\mathrm{NP}\)-hardness under all the restrictions stated above.
Return now to the general problem. Write \(d=\sum_{a\in A}|D_a|\).
Every supported type follows a path of depth at most \(m\), because attributes cannot repeat. The union of the \(\tau\) supported paths therefore contains at most \(1+m\tau\) nodes.
Starting with any legal tree, replace every subtree reached by no supported type with a leaf. Such a leaf is legal because its stopping requirement is vacuous, and the replacement changes no supported depth.
Every remaining internal node lies on a supported path. If all domain branches are explicitly represented, each internal node has at most \(d\) children. The resulting tree has \(O(1+m\tau d)\) nodes, and hence a polynomial-size encoding.
Only unsupported subtrees are removed here. A question with just one supported outcome may still change retrieval scores, so it need not be removable.
A verifier performs the following checks:
There are at most \(\tau\) supported leaves. Each retrieval computation takes \(O(nm)\) rational arithmetic operations. The denominator \(\sum_a w_a\) is common to every product, so maximizers can be computed directly from the unnormalized scores.
All arithmetic is exact. Each score combines input rationals with total encoding length at most \(L\); common denominators and score numerators have polynomially many bits. The same holds for the expected cost, since every depth is at most \(m\).
A conservative verification-time bound is
\[ O\!\left((L+m\tau d+nm\tau)\operatorname{poly}(L)\right). \]
This is polynomial in the explicit input length. Therefore the problem belongs to \(\mathrm{NP}\), completing the proof of \(\mathrm{NP}\)-completeness.
An exact dynamic program also makes the role of the explicitly listed support clear.
For each partial query \(q\), let \(T_q\) be its consistent supported types and let \(M(q)=\sum_{t\in T_q}\mu_t\). Define \(F(q)\) as the minimum *additional* expected cost from \(q\), using the original, unnormalized masses.
Set \(F(q)=0\) when \(T_q=\varnothing\), or when \(q\) is legal. Otherwise, if \(S\) is the queried attribute set,
\[ F(q)=M(q)+ \min_{a\in A\setminus S} \sum_{\substack{v\in D_a\\T_{q\cup\{a=v\}}\ne\varnothing}} F(q\cup\{a=v\}). \]
To justify the recurrence, asking \(a\) costs one question for every type in \(T_q\), contributing \(M(q)\). Its answer partitions those types into disjoint children whose optimal future costs add. Conversely, every continuation from an illegal query must begin with some unasked attribute. At a legal query, stopping costs zero and is optimal because all question costs are nonnegative.
Every complete supported query is legal, so evaluation in decreasing order of the number of queried attributes terminates.
Every nonempty-support query is the restriction of some supported type to an attribute subset. Thus there are at most \(\tau2^m\) such queries. Enumerating and deduplicating those restrictions, checking legality, and evaluating the recurrence gives the conservative deterministic bound
\[ O\!\left( \bigl[L+\tau2^m\bigl(nm+(n+m)\tau+d\bigr)\bigr] \operatorname{poly}(L) \right). \]
The answer is yes precisely when \(F(\varnothing)\leq B\). This algorithm is polynomial for fixed \(m\); the general decision problem is \(\mathrm{NP}\)-complete and therefore has no polynomial-time algorithm unless \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover’s classification is correct: the stated decision problem is \(\mathrm{NP}\)-complete, including under the claimed restrictions. The reduction, dyadic encoding, certificate argument, and dynamic program withstand verification. No major or minor mathematical issues were found.
The argument correctly restricts attention to queries with \(T_q\ne\varnothing\).
With exact-match similarities and unit weights, each consistent catalogue product has score \(|S|/m\). Every inconsistent product disagrees on at least one queried attribute and therefore has a strictly smaller score. This proves \(R(q)=T_q\), retaining every tie.
The empty query is covered: \(T_\varnothing=C=T\), and every product has score zero.
For a complete supported type \(t\), catalogue distinctness ensures that only \(t\) matches all attributes, so \(R(t)=\{t\}\). Thus a supported leaf is legal exactly when its consistent support is a singleton. The argument correctly uses equality of retrieval sets, rather than merely the presence of the intended product among the maximizers.
Finding: The stopping-rule equivalence is exact on the restricted family. It does not impose conditions on unsupported completions.
The source theorem is stated with the correct objective: the sum of object depths, rather than maximum depth or a different classification objective. The original paper defines explicitly specified binary tests, identification leaves, and total external path length as the tree cost, and establishes the corresponding decision problem’s \(\mathrm{NP}\)-completeness. [Hyafil–Rivest, 1976](https://people.csail.mit.edu/rivest/pubs/HR76.pdf)
The reduction meets these hypotheses:
Removing repeated tests along a source path is valid: the previous occurrence determines the outcome, so replacing a repeated-test node by its determined child preserves identification and cannot increase any object’s depth. This establishes the depth bound needed later.
Duplicate outcome vectors make identification impossible. The stated polynomial preprocessing of such cases, and of trivial cases, is sufficient; no difficult source instances are discarded without a decision-preserving mapping.
For unrestricted rational encodings, the uniform masses and scaled threshold give exactly the stated equivalence.
Finding: The source theorem applies, and the reduction preserves the decision problem.
All critical inequalities check out.
From \(P\geq N(Nm+1)\), the definition of \(h\) gives \(h\geq Nm+1\). Since \(0\leq r<N\), this implies \(h>rm\).
The assigned masses are positive, have power-of-two denominator, and sum to one because their total numerator is \(Nh+r=P\). The expected cost is correctly computed as \((hE+r\ell_N)/P\).
For the forward implication, the source tree can be chosen without repeated tests. Therefore \(E\leq K\) and \(\ell_N\leq m\), giving the required cost bound.
For the reverse implication, \(E>K\) implies \(E\geq K+1\), since both are integers. The nonnegative correction \(r\ell_N\), together with \(h>rm\), then makes the expected-cost numerator strictly exceed the threshold numerator. This contradicts feasibility.
The case \(r=0\) is included. The smallest suitable power of two has logarithmic bit length in \(N\) and \(m\). Including the binary encoding length of \(K\), the threshold numerator also has polynomial bit length.
Finding: The dyadic construction preserves both answers exactly and is a polynomial-time reduction.
The certificate bound correctly accommodates questions having only one supported outcome.
Every supported path has depth at most \(m\), so their union contains at most \(1+m\tau\) nodes. Replacing unsupported subtrees by leaves preserves every supported depth and is legal because those leaves have no supported types to check.
After this replacement, every internal node belongs to a supported path. Explicitly representing its domain branches adds at most \(d\) children per internal node, yielding the stated \(O(1+m\tau d)\) bound.
The prover correctly avoids removing questions merely because they do not partition the current support: such questions can still change the retrieval set.
Finding: Every yes-instance has a polynomial-size certificate.
The proposed checks verify the required tree structure, admissible questions, supported routes, leaf legality, and expected-cost threshold.
Computing complete retrieval sets \(R(t)\), then comparing each supported leaf’s \(R(q)\) against all types reaching it, checks exactly the task’s stopping condition. Unsupported leaves require no retrieval comparison.
The score normalization can be omitted when finding maximizers because its denominator is positive and common to every catalogue product. Exact rational arithmetic retains ties correctly.
There are at most \(\tau\) supported leaves, and each retrieval calculation uses at most \(O(nm)\) rational operations. Input rational products and sums have polynomial bit length. Expected-cost arithmetic also has polynomial bit length because depths are bounded by \(m\).
The stated conservative verification bound accommodates certificate traversal, retrieval calculations, and rational arithmetic.
Finding: Membership in \(\mathrm{NP}\) is established. Together with the reduction, this proves \(\mathrm{NP}\)-completeness.
The dynamic-programming state retains the full partial query, as required: the current consistent support alone need not determine \(R(q)\).
The recurrence correctly uses the original masses. Asking one question contributes \(M(q)\), and the answer branches partition the current support, so their additional costs add without conditional-probability normalization.
The stopping cases are valid:
At every illegal nonempty-support query, at least one attribute remains unasked. Every recursive transition increases the number of queried attributes, ensuring termination.
The state-count bound is valid because every nonempty-support query is a restriction of at least one supported type to an attribute subset. Consequently, at most \(\tau2^m\) distinct states need evaluation. The supplied conservative running-time expression accounts for retrieval computation, support and legality checks, and transitions, with polynomial overhead absorbed into \(\operatorname{poly}(L)\).
Finding: The exact algorithm and fixed-\(m\) polynomial-time claim are consistent with the hardness classification.
No mathematical repair or additional clarification is required. The write-up resolves the assigned problem under both rational-encoding interpretations it discusses.
⟨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.