Answer: \(\mathrm{NP}\text{-hard}\). Explicit generation can require \(2^m\) outcomes, and generation with exact minimization is possible in \(2^m\operatorname{poly}(m,\tau,L)\) time. The stated Pareto-optimality guarantee fails for this recursion.
Theorem 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateThe outcomes generated by CDCP P1 procedure are Pareto-optimal.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) binary variables, a rational distribution \(\mu\) over complete acyclic binary CP-net types, and a fixed tie-break for selecting \(Y\), run CDCP’s candidate-generation phase using the positive-mass types. Compute its shortlist \(Q_\mu\) and a member minimizing \(R_\mu(o)=\max_{t\in\operatorname{supp}(\mu)}\operatorname{rank}_t(o)\); establish whether every \(o\in Q_\mu\) is Pareto-optimal for all types in \(\operatorname{supp}(\mu)\).
Let \(V=\{X_1,\ldots,X_m\}\), with \(m\geq1\), have binary domains \(\{0,1\}\). A society is given by its support \(T\): the list of \(\tau\geq1\) distinct complete acyclic binary CP-net types, each with positive binary-rational mass, summing to \(1\). Each type has explicitly listed conditional preference tables with strict local orders; \(\tau\) is the support size, not the number of possible types. Let \(L\) be the total input bit length.
Define the candidate recursion \(F(z,S)\), where \(z\) assigns \(Z\subseteq V\) and \(S\subseteq T\). If \(Z=V\), return \(\{z\}\); if \(|S|=1\), return the completion obtained by fixing \(z\) and assigning remaining variables their locally preferred values in topological order.
Otherwise, for each \(t\in S\), let \(E_t=\{X\in V\setminus Z:\operatorname{Pa}_t(X)\subseteq Z\}\), and let \(p_t(X)\) be its preferred value under \(z\). A variable in \(\bigcup_{t\in S}E_t\) is consistent if all types eliciting it agree, and conflicting otherwise.
Choose \(Y\subseteq\bigcup_{t\in S}E_t\) intersecting every \(E_t\), first minimizing \(|Y|\), then the number of conflicting variables in \(Y\), then breaking ties lexicographically by variable indices. Let \(C\subseteq Y\) be its consistent variables. Let \(B(Y)\) contain all assignments using the agreed values on \(C\) and either binary value independently on \(Y\setminus C\).
If \(Z\cup Y=V\), return \(\{zy:y\in B(Y)\}\). Otherwise return \(\bigcup_{y\in B(Y)}F(zy,S_y)\), where \(S_y=\{t\in S:(Y\cap E_t\subseteq C)\lor(\exists X\in(Y\cap E_t)\setminus C,\ y[X]\neq p_t(X))\}\). Set \(Q_\mu=F(\varnothing,T)\); retain whole types in each branch, without splitting or reweighting their masses.
Let \(\operatorname{rank}_t(o)\) be the maximum number of improving flips on a path from \(o\) to type \(t\)'s unique optimal outcome, with rank zero at that optimum, and let \(R_\mu(o)=\max_{t\in T}\operatorname{rank}_t(o)\). Call \(o\) Pareto-optimal if no distinct outcome strictly dominates it in every support type's CP-net; incomparability does not count as weak preference.
Is deciding whether \(\exists o\in Q_\mu\) with \(R_\mu(o)\leq k\), for a binary-encoded integer \(k\geq0\), in \(\mathrm{P}\) or \(\mathrm{NP}\)-hard?
What is the complexity of explicitly computing \(Q_\mu\) and a member minimizing \(R_\mu\), with running times stated in \(m,\tau,L\) and output size where applicable?
Does every member of \(Q_\mu\) satisfy the stated Pareto-optimality condition?
For finite societies, this candidate-generation procedure has a proved Pareto-optimality guarantee, rather than a polynomial-time complexity theorem. [Discrete guarantee](https://doi.org/10.3233/978-1-60750-606-5-375).
Dominance testing for complete acyclic binary CP-nets is \(\mathrm{NP}\)-hard; this concerns a different problem. [Dominance result](https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume21/boutilier04a.pdf). No result settling this exact distribution-input shortlist optimization problem was located.
For the recursion stated in the question:
Below are proofs, including an output-sensitive generation bound. The unrestricted decision problem is also in \(\mathrm{PSPACE}\); I do not claim that it is in \(\mathrm{NP}\).
I use improving-flip dominance: an outcome strictly dominates another when a nonempty improving-flip path connects the latter to the former. This is the standard CP-net semantics. [Boutilier et al., *CP-nets*](https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume21/boutilier04a.pdf).
At a state with unassigned variables and nonempty \(S\), every \(E_t\) is nonempty. Indeed, a source of the dependency graph induced by the unassigned variables has all its parents in \(Z\). Thus a hitting set \(Y\) exists and is nonempty.
Every recursive branch has nonempty \(S_y\):
Every recursive step assigns at least one new variable. Therefore the recursion terminates, and \(Q_\mu\) is nonempty.
Different branches at a node assign different values to \(Y\), so their completed outcomes are disjoint. Writing \(q=|Q_\mu|\), the recursion tree, with terminal assignments represented as separate leaves, consequently has at most \((m+1)q\) nodes.
Fix a type \(t\) and a topological ordering \(W_1,\ldots,W_m\). Define \(b_i(o)=1\) when \(o[W_i]\) is locally preferred under its parent assignment, and \(b_i(o)=0\) otherwise.
An improving flip of \(W_i\) leaves \(b_1,\ldots,b_{i-1}\) unchanged and changes \(b_i\) from zero to one. Thus the string \(b_1(o)\cdots b_m(o)\) strictly increases lexicographically along every improving flip.
The improving graph is therefore acyclic. Its unique sink is the unique outcome with every variable locally preferred, obtained in topological order. Every improving path extends to that sink, and hence
\(\displaystyle 0\leq \operatorname{rank}_t(o)\leq 2^m-1.\)
The reduction uses constant local preferences. In such a type, let \(s\) be the vector of preferred values. Every improving flip corrects exactly one coordinate differing from \(s\), and that coordinate can never flip again. Consequently,
\(\displaystyle \operatorname{rank}_t(o)=d_H(o,s),\)
where \(d_H\) denotes Hamming distance.
Dependency arcs can still affect elicitation even when their conditional tables are constant. Such redundant arcs are permitted by the stated hypotheses.
Take a formula with \(c\geq1\) clauses, each containing three literal occurrences.
Construct a graph \(H\) with one vertex for each occurrence. Join:
Each clause forms a triangle, so an independent set contains at most one vertex per clause.
The formula is satisfiable if and only if \(H\) has an independent set of size \(c\):
Now add \(c\) isolated vertices, producing a graph \(G\) with \(m=4c\) vertices. Set \(k=2c=m/2\). Since \(\alpha(G)=\alpha(H)+c\), the formula is satisfiable if and only if \(G\) has a vertex cover of size at most \(k\).
A cover of size at most \(k\) can be extended to one of size exactly \(k\).
Consider the following binary strings of length \(m\):
Suppose \(x\) has Hamming distance at most \(k=m/2\) from both constant strings. Its weight \(w(x)\) must satisfy
\(\displaystyle w(x)\leq k,\qquad m-w(x)\leq k,\)
so \(w(x)=k\).
For an edge \(e=\{i,j\}\), let \(h_e=x_i+x_j\). Then
\(\displaystyle d_H(x,s_e)=w(x)+2-2h_e=k+2-2h_e.\)
Thus \(d_H(x,s_e)\leq k\) holds exactly when \(h_e\geq1\), meaning that the vertices selected by \(x\) cover \(e\).
Therefore a string within distance \(k\) of every listed string exists exactly when \(G\) has a vertex cover of size at most \(k\).
For every coordinate \(i\) and bit \(b\), introduce a type \(N_{i,b}\) with:
For every edge \(e\), introduce another type with the same star graph rooted at \(X_1\), and constant preferred-value vector \(s_e\).
These types satisfy all input requirements:
There are \(\tau=2m+|E(G)|\) types, and their explicit descriptions have polynomial total length.
Positive dyadic masses can be supplied as follows. Let \(D=2^{\lceil\log_2\tau\rceil}\). Give the first \(\tau-1\) types mass \(1/D\), and the final type mass \((D-\tau+1)/D\). These masses are positive, sum to one, and have polynomial encoding length.
At the initial recursion state, \(E_{N_{i,b}}=\{X_i\}\). Hence every hitting set must contain every variable, so \(Y=V\).
For each \(X_i\), the types \(N_{i,0}\) and \(N_{i,1}\) elicit opposite values. Therefore every variable is conflicting. The terminal rule gives
\(\displaystyle Q_\mu=\{0,1\}^m.\)
Since all tables are constant,
\(\displaystyle R_\mu(x)=\max\left\{d_H(x,0^m),\,d_H(x,1^m),\,\max_{e\in E(G)}d_H(x,s_e)\right\}.\)
The preceding equivalences prove
\(\displaystyle \exists x\in Q_\mu:\ R_\mu(x)\leq k \quad\Longleftrightarrow\quad \text{the original formula is satisfiable}.\)
This is a polynomial-time reduction, proving \(\mathrm{NP}\)-hardness. On this restricted family, verification consists only of Hamming-distance calculations, so the restricted decision problem is \(\mathrm{NP}\)-complete.
An algorithm returning a minimizing member in time polynomial in the input length would also solve these instances by checking its Hamming distances. Thus computing a minimizing member is \(\mathrm{NP}\)-hard.
Let \(q=|Q_\mu|\). Listing outcomes as bit strings has output size \(mq\).
At a node with \(r\) unassigned variables, exhaustive enumeration of subsets selects the prescribed \(Y\) in time
\(\displaystyle 2^r\operatorname{poly}(m,\tau,L).\)
There is also an algorithm exponential in the current support size \(s=|S|\), rather than in \(r\).
For each eligible variable, record the subset of types it covers. Process variables successively, using dynamic programming indexed by the covered subset of \(S\). Minimize the additive objective
\(\displaystyle \left(|Y|,\ |Y\setminus C|,\ -\sum_{X_i\in Y}2^{m-i}\right)\)
lexicographically. At fixed cardinality, the final component implements the required lexicographic tie-breaking: at the smallest differing index, the set containing that index is preferred.
This takes \(2^s\operatorname{poly}(m,\tau,L)\) time. Moreover, a minimum hitting set has size at most \(s\), because choosing one member of each \(E_t\) produces a hitting set of that size. Thus generating its branches also fits this bound.
The recursion-tree bound immediately gives
\(\displaystyle T_Q=O\!\left(mq\,2^\tau\operatorname{poly}(m,\tau,L)\right).\)
A second bound follows by using subset enumeration at each node. At any fixed recursion depth, the partial assignments at distinct nodes define disjoint completion sets. Therefore, if node \(v\) has \(r_v\) unassigned variables,
\(\displaystyle \sum_{v\text{ at that depth}}2^{r_v}\leq2^m.\)
There are at most \(m+1\) depths, giving
\(\displaystyle T_Q=O\!\left(m2^m\operatorname{poly}(m,\tau,L)\right).\)
Choosing the faster local hitting-set algorithm yields the combined bound
\(\displaystyle T_Q= O\!\left( \min\{m2^m,\ mq2^\tau\}\operatorname{poly}(m,\tau,L) \right).\)
These are algorithmic upper bounds, rather than claims of optimal output-sensitive complexity.
The output lower bound is unavoidable. Using only the types \(N_{i,0},N_{i,1}\) from the reduction gives \(\tau=2m\), polynomial input length, and \(q=2^m\). Explicit generation then requires at least \(\Omega(m2^m)\) bit-output operations.
For each type, enumerate its improving graph on all \(2^m\) outcomes. The code \(b_1(o)\cdots b_m(o)\) from Section 1 supplies a topological ordering.
Process outcomes in reverse order and apply
\(\displaystyle \operatorname{rank}_t(o)= \begin{cases} 0,&o=o_t^\star,\\ 1+\max_{o\to_t o'}\operatorname{rank}_t(o'),&o\neq o_t^\star. \end{cases}\)
Every nonoptimal outcome has an improving successor, and every successor has already been processed. This computes all ranks in time
\(\displaystyle \tau2^m\operatorname{poly}(m,L).\)
Maintain the maximum rank over types for each outcome, then enumerate \(Q_\mu\) and retain a member with minimum maximum rank. The total time is
\(\displaystyle T_{\mathrm{both}} =O\!\left( T_Q+\tau2^m\operatorname{poly}(m,L)+mq \right) =2^m\operatorname{poly}(m,\tau,L).\)
Processing types successively requires exponential rank storage of \(O(m2^m)\) bits, plus polynomial working storage. Explicitly retaining the shortlist adds \(O(mq)\) bits.
Membership of a proposed outcome in \(Q_\mu\) can be checked in polynomial space. At each stage, enumerate hitting sets to identify \(Y\); reject if the proposed outcome violates a consistent assignment; otherwise follow its uniquely determined branch. There are at most \(m\) stages.
Rank thresholds also admit polynomial-space checking. For \(k<2^m-1\),
\(\displaystyle \operatorname{rank}_t(o)>k \quad\Longleftrightarrow\quad \text{an improving path of length }k+1\text{ starts at }o. \)
The reverse implication uses the fact that every improving path extends to the optimum.
Existence of an improving walk of a specified length \(\ell\) between two outcomes can be evaluated recursively by enumerating a midpoint and splitting \(\ell\) into \(\lfloor\ell/2\rfloor\) and \(\lceil\ell/2\rceil\). The recursion depth is \(O(m)\), and each level stores only polynomially many bits. Acyclicity ensures that these walks are paths.
Enumerating possible candidates and checking membership and rank thresholds therefore uses polynomial space. Thus the unrestricted decision problem belongs to \(\mathrm{PSPACE}\).
Let \(A=X_1\), \(B=X_2\), \(C=X_3\), and \(D=X_4\). Give four types \(N_1,N_2,N_3,N_4\) mass \(1/4\) each.
The following table specifies every conditional preference table. Each cell contains the ordered parent tuple followed by the vector of preferred bits in lexicographic parent-assignment order. A preferred bit \(b\) means the strict order \(b\succ1-b\).
| Variable | \(N_1\) | \(N_2\) | \(N_3\) | \(N_4\) |
|---|---|---|---|---|
| \(A\) | \((D);(0,1)\) | \(\varnothing;(1)\) | \(\varnothing;(0)\) | \(\varnothing;(0)\) |
| \(B\) | \(\varnothing;(0)\) | \((A);(1,0)\) | \(\varnothing;(0)\) | \((A);(1,0)\) |
| \(C\) | \((A,B);(1,0,0,0)\) | \((A);(0,1)\) | \(\varnothing;(1)\) | \(\varnothing;(1)\) |
| \(D\) | \((B);(1,0)\) | \(\varnothing;(1)\) | \(\varnothing;(1)\) | \((A,C);(1,1,0,1)\) |
Valid topological orders are respectively \((B,D,A,C)\), \((A,D,B,C)\), \((A,B,C,D)\), and \((A,C,B,D)\). Hence all four types satisfy the hypotheses.
Outcomes below are written in coordinate order \((A,B,C,D)\).
Initially,
\(\displaystyle E_1=\{B\},\qquad E_2=\{A,D\},\qquad E_3=\{A,B,C,D\},\qquad E_4=\{A,C\}. \)
A hitting set must contain \(B\). Its only possible second variable covering both \(E_2\) and \(E_4\) is \(A\). Thus \(Y=\{A,B\}\) is the unique minimum hitting set.
Here \(B\) is consistent with preferred value zero, while \(A\) is conflicting. Follow the branch \(A=1,B=0\). The retained types are exactly \(N_1,N_3,N_4\):
At the next state,
\(\displaystyle E_1=\{C,D\},\qquad E_3=\{C,D\},\qquad E_4=\{C\}.\)
Therefore \(Y=\{C\}\). Its preferred values are zero in \(N_1\) and one in \(N_3,N_4\). Follow \(C=0\), which removes \(N_1\) and retains \(N_3,N_4\).
Only \(D\) remains. Type \(N_3\) prefers \(D=1\), whereas \(N_4\), under \(A=1,C=0\), prefers \(D=0\). The terminal rule includes both values. In particular,
\(\displaystyle o=1000\in Q_\mu.\)
For \(N_1\), the following path is improving:
\(\displaystyle 1000\to0000\to0010\to0011\to1011.\)
The four flips are justified as follows:
For each of \(N_2,N_3,N_4\), there is the improving path
\(\displaystyle 1000\to1010\to1011.\)
Indeed, all three prefer \(C=1\) at the first outcome. Types \(N_2,N_3\) unconditionally prefer \(D=1\); type \(N_4\) prefers \(D=1\) once \(A=C=1\).
Thus \(1011\) strictly dominates \(1000\) in every support type. Consequently, \(1000\) fails the stated Pareto-optimality condition.
This counterexample concerns the exact displayed recursion. The cited finite-society guarantee cannot be applied to that recursion without reconciling the procedural rules.
⟨structured verdict parsed — rendered above⟩
The output resolves the three main questions correctly: the decision problem is \(\mathrm{NP}\)-hard, explicit generation and exact minimization have the stated exponential-time upper bounds, and the displayed recursion can return an outcome that violates Pareto-optimality. I found only minor omissions in the presentation of the hardness source and the polynomial-space algorithm.
The recursion is well-defined. For each surviving type, acyclicity ensures that the graph induced by the unassigned variables has a source. Its parents are assigned, so \(E_t\neq\varnothing\). Consequently a nonempty hitting set exists.
The proof that every branch retains at least one type is correct. If there are conflicting variables, selecting any such variable identifies an eliciting type whose preferred bit differs from the branch assignment. That type satisfies the retention condition. If there are none, all types remain.
Each recursive step assigns a nonempty set of previously unassigned variables, so termination follows. The singleton completion is also well-defined because the type is acyclic.
The recursion-tree bound is correct. Sibling branches fix different assignments to the same selected set and therefore have disjoint sets of complete extensions. This disjointness persists among their descendants. With terminal outputs represented as individual leaves, depth is at most \(m\), and the bound \((m+1)q\) follows.
The rank argument is correct. In a topological order, flipping \(W_i\) cannot change the local-preference indicators of earlier variables. It changes its own indicator from zero to one; changes to later indicators do not prevent a strict lexicographic increase.
Thus the improving graph is acyclic. Its unique sink is the topologically constructed optimal outcome, and every improving path can be extended to that sink. The bound \(0\leq\operatorname{rank}_t(o)\leq 2^m-1\), and hence the claimed rank-storage bound, follow.
The occurrence-graph construction is correct, including formulas with repeated literal occurrences:
Adding \(c\) isolated vertices gives \(\alpha(G)=\alpha(H)+c\). Since \(G\) has \(4c\) vertices, the equivalence with a vertex cover of size at most \(2c\) is correct. Extending a smaller cover to exactly \(2c\) vertices is legitimate.
Minor issue: The write-up implicitly uses the NP-completeness of 3-SAT without explicitly identifying that source problem and its hardness theorem. This does not affect the reduction’s substance.
Minimum clarification: State that the reduction starts from NP-complete 3-SAT with exactly three literal occurrences per clause, allowing repetitions, and that restricting to \(c\geq1\) preserves hardness.
The calculation is correct. The two constant strings force \(w(x)=k=m/2\). For an edge incidence string,
\(d_H(x,s_e)=k+2-2(x_i+x_j)\).
Its distance is at most \(k\) exactly when at least one endpoint is selected. Consequently the Hamming constraints encode precisely the required vertex cover.
For constant conditional preferences, each improving flip permanently corrects one coordinate. The equality between rank and Hamming distance is therefore justified.
The construction satisfies the stated input requirements:
The singleton elicitation sets \(E_{N_{i,b}}=\{X_i\}\) force \(Y=V\). Each coordinate is conflicting, so the terminal rule returns every binary outcome. The reduction therefore establishes the asserted equivalence without relying on subsequent filtering.
The NP-hardness conclusion is valid. The restricted family is also in NP because rank evaluation there reduces to Hamming-distance calculations. The hardness claim for returning a minimizing member follows as stated.
Both selection algorithms are valid.
The dynamic program over subsets of the current support correctly records which types are covered. Cardinality and conflict count are additive because consistency is determined at the current state before selecting \(Y\).
The tertiary objective correctly implements the stipulated lexicographic ordering at fixed cardinality: the weight at the smallest differing index exceeds the sum of all later weights. Its binary representation has polynomial length.
A minimum hitting set has size at most \(s\), so its at most \(2^s\) branches fit the claimed local time bound.
The output-sensitive bound follows from the recursion-tree node bound.
The alternative bound also holds: partial assignments at any fixed depth have disjoint completion sets, yielding
\(\sum_v 2^{r_v}\leq2^m\).
Summing over at most \(m+1\) depths gives the stated exponential bound. Choosing the faster local selection method supports the combined minimum of the two bounds.
The exponential output example is valid. Listing \(2^m\) distinct outcomes explicitly as \(m\)-bit strings requires \(\Omega(m2^m)\) bit-output operations.
These are valid upper bounds and an output lower bound; the prover appropriately does not claim an optimal characterization of output-sensitive generation complexity.
The rank recurrence is correct because every nonoptimal outcome has an improving successor and every improving path terminates at the unique optimum.
Processing outcomes in reverse topological order therefore computes all ranks. There are \(2^m\) outcomes and at most \(m\) improving successors per outcome, so the stated time bound follows.
Taking maxima across all original support types correctly computes \(R_\mu\); it does not accidentally restrict the objective to types surviving a generation branch.
Combining these ranks with shortlist enumeration gives the claimed \(2^m\operatorname{poly}(m,\tau,L)\) total time. The exponential storage bounds are consistent with the sizes of the rank arrays and explicitly retained shortlist.
The substantive polynomial-space argument is correct. For \(k<2^m-1\), a rank exceeding \(k\) is equivalent to an improving path with \(k+1\) edges starting at the outcome. Extension to the optimum justifies the direction requiring that property.
The midpoint recursion has logarithmic depth in the requested path length, hence depth \(O(m)\), and polynomial-size data at each level. Exhaustive candidate enumeration and threshold checking preserve polynomial space.
Minor issue: Several necessary terminal cases are omitted from the algorithm sketch:
These are routine algorithm specifications, not missing mathematical ingredients.
Minimum clarification: State those terminal checks, base cases, and threshold handling explicitly.
The four tables define complete, strict, acyclic binary CP-nets. All supplied topological orders are valid.
The recursion trace is correct:
Every displayed dominance-path flip agrees with its type’s conditional table. Independent exhaustive evaluation also confirms that the shortlist is
\(Q_\mu=\{0001,0011,1000,1001,1011\}\),
and that all four displayed paths are improving.
Thus \(1011\) strictly dominates \(1000\) in every support type. This is a valid counterexample to the exact recursion’s stated Pareto property. No appeal to the cited finite-society theorem is needed for this conclusion.
The central arguments stand. The additional PSPACE claim also stands in substance, subject to routine algorithmic clarification. No major issue, false central step, or unresolved target remains.
⟨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.