d4-conf-aaai-2016-0546 (d4-conf-aaai-2016-0546)

Given \(n\) attributes, domain size \(d\), and indegree bound \(c\), let \(\Omega_{n,c,d}\) be the paper’s set of labeled acyclic CP-nets with complete, nondegenerate conditional preference tables and indegree at most \(c\). For the continuous society with \(\mu_N=1/|\Omega_{n,c,d}|\) for each \(N\in\Omega_{n,c,d}\), output a type \(N\) sampled exactly according to \(\mu\).

Let \(m=n\geq 1\), \(d\geq 2\), and \(0\leq c\leq n-1\) be integers. Let \(\Omega_{n,c,d}\) consist of CP-nets on labeled attributes \(X_1,\ldots,X_n\), each with labeled domain \(\{1,\ldots,d\}\), whose dependency graph is acyclic with indegree at most \(c\).
Each conditional preference table explicitly specifies a strict linear order for every assignment to its parents. Nondegeneracy means that every parent has two values and an assignment to the other parents for which changing between those values changes the specified order; root tables satisfy this condition vacuously. Networks are distinct when their labeled graphs or any table entry differ.
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Here the support is exactly \(\Omega_{n,c,d}\), \(\tau=|\Omega_{n,c,d}|\), and every mass is \(\mu_N=1/\tau\), so total mass is \(1\). Let \(L\) be the total input bit length; \(\tau\) denotes support size, not the number of possible types in general.
Using independent fair random bits, output an explicitly represented type \(N\) with probability exactly \(\mu_N\); measure running time in expectation.

Can this exact sampling problem be solved in expected time polynomial in \(m,\tau,L,d,c\), or is it \(\mathrm{NP}\)-hard under polynomial-time randomized oracle reductions?

Known results: Allen et al. establish exact uniform generation of these labeled, complete, nondegenerate acyclic CP-nets, with efficient generation for fixed domain size and indegree bound ([2016 result](https://cs.uky.edu/~goldsmit/papers/AAAI-16_Generating_CP-nets.pdf)). Their [2017 full version](https://www.nickmattei.net/docs/random.pdf) establishes the same uniformity result. The requested distribution is exactly this existing sampling distribution, so the stated question does not provide an unsettled continuous analogue.

1. Conclusion and interpretation

The problem is solvable in expected polynomial time, for all the stated values of \(n,d,c\).

The explicit support makes this immediate in principle: sample a uniform list index and output its entry. I prove exactness and bit complexity below, then address the intended structural distribution and its relation to the cited results.

The input is treated as promised: its support consists of every member of \(\Omega_{n,c,d}\), exactly once, with equal mass. Sampling does not require verifying that promise.

2. An exact sampler using fair bits

Write the input support as \(N_1,\ldots,N_\tau\). The edgeless graph admits \((d!)^n\) different choices of root tables, all nondegenerate. Consequently,
\(\tau\geq(d!)^n\geq2\).

Set \(k=\lceil\log_2\tau\rceil\). Use the following algorithm:

• Parse the support and count its entries to obtain \(\tau\).
• Generate \(k\) independent fair bits, interpreting them as an integer \(U\) in \(\{0,\ldots,2^k-1\}\).
• If \(U\geq\tau\), repeat step 2 with fresh bits.
• Output the complete graph and tables of \(N_{U+1}\).

All arithmetic is integer arithmetic. There is no approximation of the masses.

Exactness and termination

Each trial accepts with probability \(p=\tau/2^k\). By the definition of \(k\), \(1/2<p\leq1\).

Independence of successive trials gives probability \((1-p)^r\) of rejecting the first \(r\) trials. This tends to zero, so the algorithm terminates almost surely.

Fix an index \(i\in\{1,\ldots,\tau\}\). The event that the first \(r\) trials reject and the next produces \(U=i-1\) has probability \((1-p)^r2^{-k}\). These events are disjoint, and therefore

\(\displaystyle \Pr(\text{output }N_i)=\sum_{r=0}^{\infty}(1-p)^r2^{-k}=\frac{2^{-k}}{p}=\frac1\tau=\mu_{N_i}.\)

Thus the output distribution is exactly the requested distribution.

3. Expected bit complexity

Let \(R\) be the number of trials. Its geometric distribution gives
\(\mathbb E[R]=1/p<2\), so the expected number of random bits is less than \(2k\).

For a standard explicit list encoding, parsing the input, counting records with binary counters, locating the selected record, and copying its graph and tables can all be performed in \(O(L^2)\) bit operations. This conservative bound allows sequential scans and binary-counter operations. The selected type’s encoding has length at most \(L\), because it is already present in the input.

Generating and comparing a \(k\)-bit index takes at most \(O(k^2)\) bit operations per trial. Hence

\(\displaystyle \mathbb E[T]=O\!\left(L^2+k^2\mathbb E[R]\right)=O\!\left(L^2+(\log_2\tau)^2\right).\)

This is polynomial in \(m,\tau,L,d,c\), with \(m=n\). No fixed bound on \(d\) or \(c\) is needed.

4. The intended structural distribution

The distribution also agrees with the existing uniform CP-net generation result, rather than defining a new sampling target.

To make the structural weighting explicit, let \(\mathcal G_{n,c}\) be the labeled acyclic graphs with indegree at most \(c\). Let \(a_{p,d}\) count the nondegenerate complete tables for a specified attribute with a specified set of \(p\) parents.

Such a table is a function from \(\{1,\ldots,d\}^p\) to the set of \(d!\) strict orders. Nondegeneracy means that every input coordinate can change the output while the other coordinates remain fixed.

For \(G\in\mathcal G_{n,c}\), write \(p_i\) for the indegree of \(X_i\). The number of networks with graph \(G\) is

\(\displaystyle w(G)=\prod_{i=1}^n a_{p_i,d}.\)

Indeed, each node’s table can be chosen independently, and distinct choices give distinct networks. Every labeled network has exactly one graph, so

\(\displaystyle \tau=\sum_{G\in\mathcal G_{n,c}}w(G).\)

Consequently, a structural generator that chooses \(G\) with probability \(w(G)/\tau\) and then chooses each permissible table independently and uniformly assigns every network \(N\) with graph \(G\) probability

\(\displaystyle \frac{w(G)}{\tau}\prod_{i=1}^n\frac1{a_{p_i,d}}=\frac1\tau.\)

Allen et al.’s 2017 full version, Theorem 21, establishes precisely uniform generation over this class. Its hypotheses match the task: labeled attributes, homogeneous finite domains, complete tables, acyclic graphs, an indegree bound, and nondegeneracy defined by dependence on every parent. [2017 full version](https://www.nickmattei.net/docs/random.pdf)

The bit-complexity proof in Sections 2–3 stands independently of that result and covers varying \(d\) and \(c\) under the stated explicit-input model.

5. Interpretation of the hardness alternative

The proved classification is expected polynomial-time solvable. An unconditional assertion that the problem cannot also be \(\mathrm{NP}\)-hard under randomized oracle reductions would require an additional complexity separation.

Specifically, under the usual bounded-error interpretation of such reductions, that hardness would imply \(\mathrm{NP}\subseteq\mathrm{BPP}\). Here is why. A polynomial-time reduction makes at most \(Q\) oracle calls, each of polynomial input length. Truncate each sampler call after

\(r=\lceil\log_2(12\max\{1,Q\})\rceil\)

trials. Each truncation has probability at most \(2^{-r}\), so the probability of any truncation is at most \(1/12\), by the union bound. Until truncation, this simulation agrees exactly with the sampling oracle. Amplifying the reduction’s error to at most \(1/6\) therefore gives a polynomial-time simulation with total error at most \(1/6+1/12=1/4\).

Thus no hardness assumption is needed to settle the requested algorithmic question.

⟨structured verdict parsed — rendered above⟩

The prover resolves the stated task correctly: exact sampling takes expected polynomial time under the explicit-support input model. No mathematical repair is required.

• Input interpretation and scope. The task supplies every supported type explicitly, with equal mass. Sampling a uniform list index therefore addresses the requested distribution directly. Treating completeness, distinctness, and equal masses as promises is legitimate; the task does not require validating them. The argument does not confuse support size with the number of possible types under another input model.

• Nonempty support and boundary cases. The edgeless graph is permitted for every allowed indegree bound. Each root independently admits \(d!\) strict orders, and root nondegeneracy is vacuous. Thus \(\tau\geq(d!)^n\geq2\), as claimed. This covers \(n=1\), \(c=0\), and \(d=2\); no exceptional case is omitted.

• Rejection sampler. For \(k=\lceil\log_2\tau\rceil\), the asserted range \(2^{k-1}<\tau\leq2^k\) is correct. Consequently the acceptance probability satisfies \(1/2<p\leq1\). Fresh independent fair bits produce the required uniform candidate integer on each trial.

• Termination and exactness. Independence justifies the rejection probability \((1-p)^r\), which tends to zero. For each fixed index, the events indexed by the number of preceding rejections are disjoint and exhaust its eventual selection. The geometric-series calculation gives exactly \(2^{-k}/p=1/\tau\). When \(\tau\) is a power of two, \(p=1\) and the same calculation remains valid. Distinct list entries ensure this index distribution is also the desired type distribution.

• Expected running time and explicit output. The geometric expectation \(\mathbb E[R]=1/p<2\) is correct. For a standard explicit list encoding, the conservative \(O(L^2)\) bound accommodates parsing, binary counting, locating the record, and copying it. Its output length is at most \(L\). The \(O(k^2)\) trial bound is sufficient, and combining it with the expected trial count gives the stated expected polynomial bound. Variable \(d\) and \(c\) cause no additional enumeration cost because the support is supplied.

• Structural counting and cited result. The table-function interpretation matches the task’s quantified nondegeneracy condition: each parent coordinate must affect the output for some fixed assignment of the other coordinates. Independent table choices justify \(w(G)=\prod_i a_{p_i,d}\), and partitioning networks by their labeled graphs justifies the sum for \(\tau\). The conditional sampling calculation correctly assigns probability \(1/\tau\) to each network.

The citation is accurate. Theorem 21 states uniform generation, and the surrounding definitions specify acyclic graphs, homogeneous domains, complete tables, and nondegeneracy through dependence on every parent. These hypotheses match the task. The prover uses this result for distributional agreement, while its running-time proof remains independent. [Allen et al., Sections 3.2–3.4 and Theorem 21](https://www.nickmattei.net/docs/random.pdf)

• Hardness discussion. Under the stated usual bounded-error interpretation, the simulation argument is correct. For promise-respecting oracle calls, each truncation probability is at most \(2^{-r}\); the union bound gives at most \(1/12\) across \(Q\) calls, including adaptive calls. Here \(Q\) must bound the calls of the amplified reduction, consistent with the argument’s interpretation. Combining reduction error \(1/6\) with simulation failure probability \(1/12\) gives \(1/4\). The prover appropriately avoids claiming an unconditional exclusion of randomized-oracle hardness.

Issues and actionable feedback: None. The central algorithm, probability calculation, complexity bound, and connection to the known distribution are all verifiable as written.

⟨structured verdict parsed — rendered above⟩