Answer: Polynomial-time solvable.
Proposition 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet X be a set of binary attributes. Algo- rithm 1, when restricted to linear LP-trees, always returns the linear tree L that minimizes the empirical expected rank rank(≻L, H).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(n\) binary product attributes and a support \(S\subseteq\{0,1\}^n\) of size \(\tau\), with positive rational masses \(\mu_o\) summing to \(1\) that represent the fractions of a one-purchase customer cohort selecting each configuration, find a complete linear LP-tree \(L\) minimizing \(R_\mu(L)=2^{-n}\sum_{o\in S}\mu_o\,\operatorname{rank}(L,o)\).
Let \(m=n\geq 1\) be the number of binary product attributes, with configuration domain \(\{0,1\}^m\).
A society is given by its support: a list \(S\) of \(\tau\) distinct configuration types with positive masses \(\mu_o\) encoded as binary rationals, satisfying \(\sum_{o\in S}\mu_o=1\). Here \(\tau=|S|\) is the support size, not the number of possible types; let \(L\) be the total input bit length.
A complete linear LP-tree \(T\) consists of a permutation of all attributes and an unconditional strict preference between the two values of each attribute. Configurations are compared lexicographically using these choices; no grouped attributes or conditional preferences are allowed.
Let \(\operatorname{rank}(T,o)\) be the position of \(o\) among all \(2^m\) configurations, with the best ranked \(1\). Find a tree minimizing \(R_\mu(T)=2^{-m}\sum_{o\in S}\mu_o\operatorname{rank}(T,o)\); any minimizing tree is acceptable.
Is exact minimization of \(R_\mu\) over complete linear LP-trees solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For a nonempty finite multiset of positive examples over binary attributes, a polynomial-time algorithm finds a complete linear LP-tree minimizing the normalized empirical mean rank.
Exact minimization is polynomial-time solvable in \(m,\tau,L\). Choose a majority-preferred value for each attribute, then order the attributes by increasing mass of configurations having the nonpreferred value.
The proof uses precisely the stated restriction to single attributes with unconditional preferences.
Write a tree as an attribute permutation \(\pi(1),\ldots,\pi(m)\), together with a preferred value \(b_j\in\{0,1\}\) for each attribute \(j\). For a configuration \(o\), define \(d_j(o)=\mathbf{1}\{o_j\ne b_j\}\).
Under the tree’s lexicographic order, the mismatch vectors \((d_{\pi(1)}(o),\ldots,d_{\pi(m)}(o))\) are ordered lexicographically with zero preferred to one. The mapping from configurations to mismatch vectors is a bijection onto \(\{0,1\}^m\). Their lexicographic order is their order as binary integers, with the first coordinate most significant. Consequently,
\(\displaystyle \operatorname{rank}(T,o)=1+\sum_{k=1}^{m}2^{m-k}d_{\pi(k)}(o).\)
For each attribute and possible preferred value, let
\(\displaystyle q_j(b)=\sum_{o\in S}\mu_o\,\mathbf{1}\{o_j\ne b\}.\)
Substituting the rank formula, interchanging finite sums, and using \(\sum_{o\in S}\mu_o=1\) gives
\(\displaystyle R_\mu(T)=2^{-m}+\sum_{k=1}^{m}2^{-k}q_{\pi(k)}(b_{\pi(k)}).\)
Thus the objective depends only on the marginal masses of individual attributes.
Define the marginal masses
\(\displaystyle p_j(v)=\sum_{\substack{o\in S\\o_j=v}}\mu_o,\qquad v\in\{0,1\}.\)
They satisfy \(p_j(0)+p_j(1)=1\). Since \(q_j(0)=p_j(1)\) and \(q_j(1)=p_j(0)\), the minimum possible mismatch mass for attribute \(j\) is
\(\displaystyle q_j=\min\{p_j(0),p_j(1)\}.\)
For any fixed permutation, each preference choice occurs in exactly one summand of the objective, with a strictly positive coefficient. Therefore, choosing a value of maximum marginal mass for every attribute minimizes the objective for that permutation. Either preferred value is acceptable when the marginal masses tie.
It remains to minimize
\(\displaystyle 2^{-m}+\sum_{k=1}^{m}2^{-k}q_{\pi(k)}\)
over permutations.
Suppose two adjacent positions \(k,k+1\) contain attributes \(a,b\) with \(q_a>q_b\). The contribution before swapping minus the contribution after swapping is
\(\displaystyle \bigl(2^{-k}q_a+2^{-(k+1)}q_b\bigr)-\bigl(2^{-k}q_b+2^{-(k+1)}q_a\bigr)=2^{-(k+1)}(q_a-q_b)>0.\)
Hence swapping an adjacent inversion strictly improves the objective. Repeatedly swapping such inversions terminates at a permutation satisfying
\(\displaystyle q_{\pi(1)}\le q_{\pi(2)}\le\cdots\le q_{\pi(m)}.\)
Every permutation can be sorted this way. All sorted permutations have the same sequence of mismatch masses, including multiplicities, and therefore the same objective value. Thus every such sorted permutation is globally optimal.
This also covers \(m=1\), for which only the preference choice matters.
The algorithm is:
To verify polynomial bit complexity, write each input mass as \(\mu_o=a_o/b_o\), where \(a_o,b_o\) are positive integers encoded in binary. Set
\(\displaystyle D=\prod_{o\in S}b_o,\qquad W_o=a_o(D/b_o).\)
The division is exact. The bit length of \(D\) is at most one plus the sum of the bit lengths of the input denominators, hence is \(O(L)\). Moreover, \(W_o=D\mu_o\), so the mass normalization implies
\(\displaystyle \sum_{o\in S}W_o=D.\)
Thus every \(W_o\), and every partial sum of these nonnegative weights, has \(O(L)\) bits.
For each attribute, compute the integer
\(\displaystyle A_j=\sum_{\substack{o\in S\\o_j=1}}W_o.\)
Then \(p_j(1)=A_j/D\), \(p_j(0)=(D-A_j)/D\). Choose preferred value zero when \(A_j\le D-A_j\), and one otherwise. Sorting the integers
\(\displaystyle Q_j=\min\{A_j,D-A_j\}\)
is equivalent to sorting the mismatch masses \(q_j=Q_j/D\).
Computing the common denominator and weights takes polynomial time in \(\tau,L\). Accumulating the marginal weights requires \(O(m\tau)\) integer additions, and sorting requires \(O(m\log m)\) integer comparisons. All these integers have \(O(L)\) bits, so the entire algorithm runs in polynomial time in \(m,\tau,L\).
If the optimal objective value is also desired, it is exactly
\(\displaystyle R_\mu^{\min}=\frac{D+\sum_{k=1}^{m}2^{m-k}Q_{\pi(k)}}{2^mD},\)
whose numerator and denominator have \(O(L+m)\) bits.
For a nonempty multiset of examples, assigning each configuration type its relative frequency produces the stated empirical objective. The argument above proves that case and extends it directly to binary-encoded rational masses through exact marginal computations. No expansion into a multiset is needed.
⟨structured verdict parsed — rendered above⟩
The output fully resolves the task. Its rank identity, optimization argument, and exact arithmetic analysis are correct under the stated restriction to complete linear LP-trees with unconditional preferences. No major or minor issues were found.
Every allowed tree is represented by an attribute permutation \(\pi\) and one preferred binary value \(b_j\) for each attribute. This matches the task exactly.
For fixed preferences, the coordinatewise mismatch map is a bijection on \(\{0,1\}^m\). Lexicographic comparison of mismatch vectors, with zero preferred, agrees with increasing binary integer order. Therefore the formula
\[
\operatorname{rank}(T,o)=1+\sum_{k=1}^{m}2^{m-k}d_{\pi(k)}(o)
\]
is correct, including the indexing convention that the best configuration has rank \(1\).
Substituting the rank formula and exchanging finite sums correctly yields
\[
R_\mu(T)=2^{-m}+\sum_{k=1}^{m}2^{-k}q_{\pi(k)}(b_{\pi(k)}).
\]
The constant term uses the supplied normalization \(\sum_{o\in S}\mu_o=1\). Consequently, correlations between attributes do not affect this objective. This conclusion follows directly from the displayed identity.
The identities \(q_j(0)=p_j(1)\) and \(q_j(1)=p_j(0)\) are correct.
For every fixed permutation, each preference affects only its own summand, whose coefficient is positive. Thus choosing a majority-preferred value independently for each attribute minimizes the objective for that permutation. Since these choices work for every permutation, this reduction also preserves global optimality.
Tied marginals are handled correctly: either preference produces the same mismatch mass.
The adjacent-swap computation is correct:
\[
2^{-(k+1)}(q_a-q_b)>0
\]
when \(q_a>q_b\). Thus an adjacent inversion strictly worsens the objective.
The sorting argument establishes global optimality: every permutation can be transformed into a nondecreasing order without increasing the objective, and all such sorted orders have the same sequence of mismatch masses. Equal masses cause no difficulty. The case \(m=1\) is explicitly and correctly covered.
The denominator construction is valid even when the input fractions are unreduced. Each denominator divides \(D\), so every \(W_o=a_o(D/b_o)\) is an integer.
The product \(D\) has \(O(L)\) bits. Normalization gives \(\sum_o W_o=D\); positivity therefore bounds every weight and marginal partial sum by \(D\). The divisions and multiplications used to construct the weights also involve integers of polynomial bit length.
The marginal computations require \(O(m\tau)\) additions, and sorting uses \(O(m\log m)\) comparisons, all on \(O(L)\)-bit integers. Standard exact integer arithmetic therefore gives polynomial running time in \(m,\tau,L\). The returned permutation and preferences provide the required complete tree.
The optional optimal-value formula is algebraically correct, and its numerator and denominator have \(O(L+m)\) bits.
Aggregating a nonempty multiset into distinct configurations with relative-frequency masses preserves its empirical mean rank. The stated correspondence is correct.
The proof addresses arbitrary valid rational masses directly; it does not rely on expanding binary-encoded weights into a potentially large multiset. No external theorem is invoked that requires additional hypotheses.
No repair or additional clarification is needed.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.