d4-conf-aaai-2015-0588 (d4-conf-aaai-2015-0588)

Fix \(K \in \{\mathrm{UI\text{-}FP}, \mathrm{UI\text{-}UP}, \mathrm{UI\text{-}CP}\}\). An instance gives \(p\), a finite support \(E\) of labeled comparisons \(e=(\alpha,\beta,v)\) over \(\{0,1\}^p\), positive binary-rational masses \(\mu_e\) summing to \(1\), and a rational threshold \(q \in [0,1]\). Does there exist a tree \(T \in K\) that satisfies comparisons of total mass at least \(q\), that is, \(\sum_{e \in E:\,T\text{ satisfies }e}\mu_e \ge q\)?

Fix \(K\in\{\mathrm{UI\text{-}FP},\mathrm{UI\text{-}UP},\mathrm{UI\text{-}CP}\}\). There are \(p\ge1\) binary issues and outcomes in \(\{0,1\}^p\).
A partial lexicographic preference tree is a finite ordered binary tree: each internal node tests an issue and prefers either \(1\) or \(0\); no issue repeats along a root-to-leaf path. An outcome follows the left child for the preferred value and the right child otherwise. Its rank \(r_T(\alpha)\) is the position of its leaf in left-to-right leaf order.
A tree is collapsible if some ordering of its used issues contains every root-to-leaf issue sequence as a subsequence. In \(\mathrm{UI\text{-}FP}\), every path has the same issue sequence and every node prefers \(1\). In \(\mathrm{UI\text{-}UP}\), every path has the same issue sequence and all occurrences of each issue share a preferred value. The class \(\mathrm{UI\text{-}CP}\) consists of the remaining collapsible trees. Paths may omit issues; a single leaf is allowed in the first two classes. There is no tree-size bound.
A comparison type is \(e=(\alpha,\beta,v)\), with distinct outcomes \(\alpha,\beta\) and \(v\in\{0,1\}\). It is satisfied when \(r_T(\alpha)<r_T(\beta)\) for \(v=1\), or \(r_T(\alpha)=r_T(\beta)\) for \(v=0\).
A society is given by its support: the list \(E\) of its \(\tau\) comparison types with positive binary-rational masses \(\mu_e\), where \(\sum_{e\in E}\mu_e=1\). Here \(\tau\) is the support size, not the number of possible types. The input also includes a binary-rational threshold \(q\in[0,1]\). Let \(m=p\) denote the number of issues and \(L\) the total input bit length; state running times in \(m,\tau,L\).

For each fixed \(K\), is deciding whether there exists \(T\in K\) with \(\sum_{e\in E:\,T\text{ satisfies }e}\mu_e\ge q\) solvable in polynomial time, or is it NP-hard?

The unweighted discrete problem of satisfying at least a given number of comparisons is NP-complete for each of these three classes ([Liu and Truszczynski, 2015](https://ojs.aaai.org/index.php/AAAI/article/download/9403/9262)).
No separate result for this exact normalized rational-mass formulation was located.

For every fixed \(K\in\{\mathrm{UI\text{-}FP},\mathrm{UI\text{-}UP},\mathrm{UI\text{-}CP}\}\), the decision problem is NP-complete, and hence NP-hard. Normalization of the masses does not remove the unweighted hardness.

1. The known result and its applicability

We use the supplied unweighted NP-completeness result: given a set \(E\) of distinct comparison types and an integer \(k\), with \(1\le k\le |E|\), deciding whether some \(T\in K\) satisfies at least \(k\) members of \(E\) is NP-complete.

This is Theorem 6 of [Liu and Truszczynski (2015)](https://ojs.aaai.org/index.php/AAAI/article/download/9403/9262). Its definitions match the present task: binary issues, strict and indifference comparisons, collapsibility, and the three stated preference classes. In particular, the paper defines \(\mathrm{UI\text{-}CP}\) as the remaining collapsible trees.

The reduction below uses this theorem as its hardness premise.

2. Reduction to normalized rational masses

Fix \(K\), and take an unweighted instance \((E,k)\), where \(\tau=|E|\). Retain exactly the same issues and comparison types, and set

\(\mu_e=1/\tau\quad(e\in E),\qquad q=k/\tau.\)

All masses are positive and sum to \(1\). For every admissible tree \(T\),

\(\displaystyle \sum_{e\in E:\,T\text{ satisfies }e}\mu_e =\frac{|\{e\in E:T\text{ satisfies }e\}|}{\tau}.\)

Consequently, the weighted score is at least \(q\) if and only if \(T\) satisfies at least \(k\) comparisons. The admissible trees are unchanged, so this equivalence holds separately for each fixed \(K\).

If rationals are represented by binary numerators and denominators, each new mass and the threshold require \(O(\log(\tau+1))\) bits. Thus this is a polynomial-time many-one reduction.

The following construction also handles the stricter interpretation that “binary-rational” means a dyadic rational, with a finite binary expansion.

Enumerate \(E=\{e_1,\ldots,e_\tau\}\). Let \(D\) be the smallest power of two satisfying \(D\ge\tau^2\), and write

\(D=a\tau+b,\qquad a=\lfloor D/\tau\rfloor,\qquad 0\le b<\tau.\)

Then \(a\ge\tau\). Assign

\(\mu_{e_i}=(a+1)/D\) for \(1\le i\le b\), and \(\mu_{e_i}=a/D\) otherwise, and set \(q=ka/D\).

These masses are positive dyadic rationals, and

\(\displaystyle \sum_{i=1}^{\tau}\mu_{e_i} =\frac{b(a+1)+(\tau-b)a}{D}=1.\)

Also, \(0<q\le1\), since \(k\le\tau\) and \(a\tau\le D\).

Suppose \(T\) satisfies exactly \(t\) comparisons.

• If \(t\ge k\), its score is at least \(ta/D\ge ka/D=q\).
• If \(t\le k-1\), its score is at most \((k-1)(a+1)/D<ka/D=q\). The strict inequality follows from

\(ka-(k-1)(a+1)=a-(k-1)\ge\tau-k+1\ge1.\)

Thus the reduction is valid even with exclusively dyadic masses and threshold.

Because \(D\le2\tau^2\), all added numbers have \(O(\log(\tau+1))\) bits. With explicit outcome strings, this construction takes \(O(m\tau+\tau\log^2(\tau+1))\) bit operations using elementary arithmetic, and produces an instance of length \(O(m\tau+\tau\log(\tau+1))\).

This proves NP-hardness for all three classes.

3. Polynomial certificates despite unbounded tree size

We now prove membership in NP for arbitrary input masses.

For \(\mathrm{UI\text{-}FP}\), a certificate is the common sequence of distinct issues. For \(\mathrm{UI\text{-}UP}\), it additionally specifies one preferred bit per issue. Each certificate describes the corresponding full binary tree implicitly.

To compare two outcomes, inspect this sequence until the first issue on which they differ. Its preferred bit determines their strict order. If no selected issue distinguishes them, they reach the same leaf. Each comparison therefore requires at most \(m\) issue inspections.

For \(\mathrm{UI\text{-}CP}\), we need a compression argument that preserves both the comparisons and membership in the residual class.

Compression lemma. If a tree \(T\in\mathrm{UI\text{-}CP}\) exists, there is a tree \(T'\in\mathrm{UI\text{-}CP}\) with at most \(2(2\tau+2)m+1\) nodes that induces exactly the same strict-order and equality relations on all comparisons in \(E\).

Proof. Let \(S\) contain all outcomes appearing in \(E\), so \(|S|\le2\tau\). Select every root-to-leaf path followed by an outcome in \(S\).

Since \(\mathrm{UI\text{-}FP}\subseteq\mathrm{UI\text{-}UP}\), the tree \(T\) fails at least one defining condition of \(\mathrm{UI\text{-}UP}\):

• Two root-to-leaf paths have different issue sequences; or
• Two nodes testing the same issue have different preferred bits.

In the first case, also select those two paths. In the second case, select a root-to-leaf path through each of the two nodes. Thus at most \(2\tau+2\) paths have been selected.

Replace every subtree containing no selected leaf by a single leaf. Call the resulting tree \(T'\). Every selected path remains unchanged.

There are at most \((2\tau+2)m\) retained internal nodes: each belongs to a selected path, and each such path contains at most \(m\) internal nodes. A full binary tree with \(n\) internal nodes has \(2n+1\) nodes, giving the claimed bound.

Every path of \(T'\) is an original path or an initial segment of one. Hence the original issue ordering witnesses collapsibility of \(T'\), after restriction to its used issues.

The selected witnesses to failure of \(\mathrm{UI\text{-}UP}\) survive unchanged. Therefore \(T'\) remains in \(\mathrm{UI\text{-}CP}\).

Finally, two outcomes in \(S\) that originally reached the same leaf still do so. If they reached different leaves, their first branching node remains, and their left-to-right order is preserved. Thus every comparison in \(E\) has exactly its original satisfaction status. \(\square\)

A certificate for this class consists of \(T'\) and an ordering of its used issues. The verifier checks the tree structure, increasing issue positions along each path, and failure of the \(\mathrm{UI\text{-}UP}\) conditions. It then evaluates all supported comparisons.

4. Exact verification and conclusion

After determining the satisfied comparisons, the verifier sums their masses exactly and compares the sum with \(q\).

A common denominator obtained by multiplying the input denominators has bit length \(O(L)\): its bit length is bounded by the sum of their encoded bit lengths. Consequently, elementary integer arithmetic suffices for exact verification in polynomial time.

Combining certificate construction, structural checks, comparison evaluation, and arithmetic, a straightforward implementation has the conservative verification bound

\(O\bigl((m(\tau+1)+L)^3\bigr)\)

in bit operations. This establishes membership in NP for every fixed \(K\).

Together with the reduction, all three problems are NP-complete. A polynomial-time algorithm for any one of them would imply \(\mathrm{P}=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

Verification report

The prover resolves the task correctly for all three fixed classes. Both reductions preserve the decision answer, including under the interpretation that binary-rational numbers must be dyadic. The certificate argument establishes membership in \(\mathrm{NP}\) despite the absence of a tree-size bound. No major or minor mathematical issues were found.

1. Cited hardness premise

The cited theorem is applicable as stated.

Definition 3 in the paper defines MAXLEARN using a set of comparison examples and a positive integer threshold bounded by the number of examples. Theorem 6 states NP-completeness for the three classes under consideration. The paper’s definitions also match the task’s binary issues, strict and indifference comparisons, collapsibility, common issue sequences for the first two classes, and residual definition of \(\mathrm{UI\text{-}CP}\). [Liu and Truszczynski (2015)](https://ojs.aaai.org/index.php/AAAI/article/download/9403/9262)

The distinction between a collapsed representation in the paper and an explicit tree in the task does not invalidate this application: the representations describe the same admissible trees, and the task imposes no representation-size bound.

The prover therefore correctly uses the supplied unweighted result without needing to reproduce its hardness proof.

2. Uniform-mass reduction

The source restrictions imply \(\tau\ge1\), so the denominators are nonzero.

For binary numerator-and-denominator encoding, the assignments \(\mu_e=1/\tau\) and \(q=k/\tau\) satisfy all input requirements:

• Every mass is positive.
• Their sum is exactly \(1\).
• The threshold belongs to \([0,1]\).
• The comparison types and admissible trees are unchanged.

The score identity in the output is exact. Consequently, the weighted threshold holds precisely when the number of satisfied comparisons is at least \(k\). This proves both directions of the many-one reduction separately for each fixed class.

The stated encoding length per rational is correct. Uniform masses need not be dyadic, but the prover explicitly limits this construction to general binary-encoded rationals and supplies a separate dyadic construction.

3. Dyadic reduction

All computations and inequalities in this construction are correct.

Because \(D\ge\tau^2\), the quotient \(a=\lfloor D/\tau\rfloor\) satisfies \(a\ge\tau\). The remainder satisfies \(0\le b<\tau\). Thus every assigned mass is positive and dyadic.

The normalization calculation is valid: the sum of the mass numerators is \(a\tau+b=D\). The threshold is also admissible because \(1\le k\le\tau\) and \(a\tau\le D\).

For a tree satisfying \(t\) comparisons:

• When \(t\ge k\), every satisfied comparison contributes at least \(a/D\), giving score at least \(q\).
• When \(t\le k-1\), every contribution is at most \((a+1)/D\), giving the displayed upper bound.

The strict separation is verified by
\[ ka-(k-1)(a+1)=a-k+1\ge\tau-k+1\ge1. \]
Thus no source no-instance becomes a target yes-instance.

The bound \(D\le2\tau^2\) is valid, including \(\tau=1\). The claimed bit lengths, output length, and construction time are consistent with elementary binary arithmetic and explicit outcome strings.

4. Certificates for the first two classes

The sequence certificates correctly describe every admissible tree in \(\mathrm{UI\text{-}FP}\) and \(\mathrm{UI\text{-}UP}\). Their common root-to-leaf sequence determines the full binary structure implicitly; the preferred bits determine the branch ordering.

The comparison procedure is correct. The first selected issue on which the outcomes differ determines their strict leaf order. If none differs, they reach the same leaf.

The certificate length is polynomial, and each comparison requires at most \(m\) issue inspections. The empty sequence covers the permitted single-leaf tree.

5. Compression lemma for the residual class

The lemma is correct, including its preservation of residual-class membership.

• Witness selection. Since \(\mathrm{UI\text{-}FP}\subseteq\mathrm{UI\text{-}UP}\), a residual-class tree must violate either the common-sequence condition or the issuewise preferred-bit condition. Each violation has witnesses on at most two root-to-leaf paths.

• Path bound. Adding those witnesses to the paths for supported outcomes selects at most \(2\tau+2\) paths.

• Pruning. A subtree with no selected leaf cannot contain any part of a selected root-to-leaf path. Replacing it by a leaf therefore preserves every selected path completely.

• Size bound. Each retained internal node belongs to a selected path, and each path contains at most \(m\) internal nodes. The full-binary-tree node count gives exactly the claimed upper bound.

• Collapsibility. Every resulting path is an original path or its prefix. The original issue ordering, restricted to retained issues, remains a valid witness.

• Residual membership. Both kinds of selected violation witnesses survive unchanged, so the pruned tree cannot enter \(\mathrm{UI\text{-}UP}\).

• Comparison preservation. Supported outcomes retain their original leaves. Equality is preserved, and distinct supported leaves retain their left-to-right order.

The certificate and structural checks described after the lemma therefore suffice.

6. Exact arithmetic and running time

Multiplying the input denominators produces a common denominator with bit length \(O(L)\). This remains true when the threshold denominator is included. Exact summation and threshold comparison consequently require only polynomially many bit operations.

The compressed tree has \(O(m(\tau+1))\) nodes. Its encoding, membership checks, and supported-comparison evaluation are polynomially bounded. The stated conservative verification bound \(O((m(\tau+1)+L)^3)\) accommodates these operations and elementary exact arithmetic.

The endpoint thresholds \(q=0\) and \(q=1\) cause no verification problem. An empty residual class for a small issue domain likewise causes no gap: certificate verification still rejects all invalid witnesses.

The NP-completeness conclusion follows. No additional clarification or repair is required.

⟨structured verdict parsed — rendered above⟩