Answer: \(\mathrm{NP}\text{-hard}\) for every fixed \(k\ge 2\).
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFix a constant integer k ≥2. Deciding whether there exists a CP-net in Nk that entails all pairwise compar- isons in a set P is NP-hard, even if for every o1 ≻o2 ∈P, o1, o2 differ on at most two variables, and even if when some CP-net entails all comparisons in P, then there also exists a CP-net N ∈N2 that entails all comparisons in P.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given Boolean variables \(V\), fixed \(k\ge 2\), and a support of report types \(q=(o_q^+,o_q^-)\) with positive rational masses \(\mu_q\) summing to \(1\), does there exist an acyclic \(N\in\mathcal N_k\) such that \(N\models o_q^+\succ o_q^-\) for every support type \(q\)?
Let \(V\) contain \(m\) Boolean variables, with outcomes in \(\{0,1\}^{V}\), and fix a constant integer \(k\ge2\).
A society is given by its support: a list of \(\tau\) distinct report types \(q=(o_q^+,o_q^-)\), each consisting of two distinct outcomes and having positive binary rational mass \(\mu_q\), with \(\sum_q\mu_q=1\). Here \(\tau\) is the support size, not the number of possible types; let \(L\) be the total input bit length.
A CP-net specifies a directed graph on \(V\) and, for every variable and every assignment to its parents, a strict total order on its Boolean values. Let \(\mathcal N_k\) consist of such CP-nets whose graphs are acyclic and have maximum in-degree at most \(k\).
A total preorder on outcomes satisfies a CP-net when it strictly prefers the locally preferred value in every parent context, holding all other variables fixed. Write \(N\models o\succ o'\) when every total preorder satisfying \(N\) strictly prefers \(o\) to \(o'\).
The decision problem asks whether one \(N\in\mathcal N_k\) entails \(o_q^+\succ o_q^-\) for every support type; inputs are not promised to admit such a network.
For each fixed \(k\ge2\), is this decision problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finite comparison sets, this existence problem is NP-hard for every fixed \(k\ge2\), even for Boolean outcomes differing on at most two variables and with a promise that every feasible instance has an in-degree-two solution ([original result](https://www.ijcai.org/Proceedings/09/Papers/313.pdf)).
No result explicitly treating the specified rational-mass support problem was located.
For every fixed \(k\ge 2\), the decision problem is NP-hard, even when all masses are dyadic rationals and every reported pair differs on at most two variables. Consequently, a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm P=\mathrm{NP}\).
The proof transfers the stated comparison-set hardness theorem to the support representation. No new hardness construction is needed.
Theorem 1 of Dimopoulos, Michael, and Athienitou states that, for each fixed \(k\ge 2\), deciding whether a finite comparison set \(P\) is entailed by an acyclic CP-net of maximum in-degree at most \(k\) is NP-hard. Its hard instances use Boolean variables, comparisons differing on at most two variables, and have the additional property that whenever they are feasible, an in-degree-two solution exists. [Original paper, Theorem 1](https://www.ijcai.org/Proceedings/09/Papers/313.pdf).
The paper’s Definitions 1–3 use strict local orders and define entailment by quantifying over every total preorder satisfying the local ceteris paribus preferences. Its class \(\mathcal N_k\) is the class of acyclic CP-nets with maximum in-degree at most \(k\). Thus the theorem uses exactly the network class and entailment semantics in the question. [Original paper, Section 2](https://www.ijcai.org/Proceedings/09/Papers/313.pdf).
We apply this theorem separately for each fixed \(k\); hardness for a smaller network class alone would not justify hardness for a larger one.
Fix \(k\ge 2\). Let \((V,P)\) be an instance of the comparison-set problem, with nonempty comparison set
\(P=\{o_i^+\succ o_i^-:1\le i\le s\}\).
Repeated identical comparisons, if present in an input list, can be removed in polynomial time: repetition does not change which networks entail all comparisons. The comparisons in the cited hard instances have distinct outcomes within each pair.
Retain the variable set \(V\), and create one support type \(q_i=(o_i^+,o_i^-)\) per comparison. Hence \(\tau=s\), and the report types are distinct.
To ensure that the masses qualify even under a restriction to terminating binary fractions, put
\(r=\lceil\log_2 s\rceil\),
and assign
\(\mu_{q_i}=2^{-r}\) for \(1\le i<s\), and
\(\mu_{q_s}=(2^r-s+1)2^{-r}\).
These masses satisfy every required condition:
\(\sum_{i=1}^{s}\mu_{q_i}=(s-1)2^{-r}+(2^r-s+1)2^{-r}=1\).
For \(s=1\), this construction gives the single mass \(1\).
If the source comparison set is empty, map it to the fixed feasible support consisting of one Boolean variable \(x\), the comparison \(1\succ 0\), and mass \(1\). This preserves the affirmative answer for an empty comparison set.
For a nonempty source instance, every candidate \(N\in\mathcal N_k\) satisfies
\(N\models o_q^+\succ o_q^-\) for every support type \(q\)
if and only if
\(N\models o_i^+\succ o_i^-\) for every comparison in \(P\).
This equivalence holds because the support contains exactly those ordered pairs. The decision predicate imposes no further condition involving their masses. Taking the existential quantifier over \(N\in\mathcal N_k\) therefore preserves both affirmative and negative answers.
The reduction preserves the outcomes, so it preserves the bound of two differing variables per comparison. It also preserves the set of feasible networks, and hence the cited property that every feasible hard instance has an in-degree-two solution.
We have thus given a polynomial-time many-one reduction from the cited NP-hard problem to the specified rational-mass support problem. This proves the requested NP-hardness classification. It does not assert membership in \(\mathrm{NP}\), which is unnecessary for the question.
⟨structured verdict parsed — rendered above⟩
The prover’s argument is correct and resolves the assigned problem. The cited hardness theorem matches the required network class and entailment semantics, and the reduction to rational-mass supports preserves feasibility in polynomial time. No major or minor mathematical issues were found.
Theorem 1 explicitly fixes an arbitrary constant integer \(k\ge 2\) and asserts NP-hardness of deciding whether some network in \(\mathcal N_k\) entails every comparison in a finite set. It also states both advertised restrictions: each comparison changes at most two variables, and feasible instances admit a solution in \(\mathcal N_2\). The theorem’s construction uses two-element variable domains, which can be labeled \(\{0,1\}\). Thus the Boolean restriction is justified. This is a decision theorem without a promise of feasibility. [Original paper, Theorem 1](https://www.ijcai.org/Proceedings/09/Papers/313.pdf).
The prover correctly applies this theorem separately for each fixed \(k\). It does not infer hardness for larger network classes merely from hardness for \(\mathcal N_2\).
The paper defines preference rankings as total preorders, specifies strict total orders in the conditional preference tables, and requires the local strict comparison in every parent context while fixing all other variables. Entailment quantifies over every satisfying ranking. Its notation \(\mathcal N_k\) denotes acyclic networks with maximum in-degree at most \(k\). These definitions match the task. [Original paper, Section 2](https://www.ijcai.org/Proceedings/09/Papers/313.pdf).
No conversion between different notions of entailment or network feasibility is left unproved.
Removing repeated identical comparisons preserves their conjunction and takes polynomial time. After this preprocessing, one support type per ordered comparison gives distinct report types and \(\tau=s\).
Each comparison in the cited hard family has distinct outcomes within its pair. Opposite comparisons, if both occur, remain distinct ordered report types; their possible inconsistency does not invalidate the construction because the target accepts infeasible inputs.
With \(r=\lceil\log_2 s\rceil\), one has \(s\le 2^r\). Therefore the last numerator \(2^r-s+1\) is at least \(1\), and all masses are positive.
The normalization calculation is exact:
\[ (s-1)2^{-r}+(2^r-s+1)2^{-r}=1. \]
Every mass is dyadic and consequently has a terminating binary representation. For \(s=1\), the construction gives \(r=0\) and the sole mass \(1\). For powers of two, all masses equal \(1/s\). There is no exceptional case that violates positivity or normalization.
Both \(2^r\) and the last numerator have \(O(1+\log s)\) binary digits. Writing all masses therefore takes \(O(s(1+\log s))\) bits, and explicitly writing the paired Boolean outcomes takes \(O(sm)\) bits.
Deduplication, computing \(r\), forming these binary integers, and copying the outcomes all take polynomial time. Ordinary variable identifiers and delimiters add only polynomial overhead. Thus the reduction produces an instance whose total bit length is polynomial in the explicitly encoded source instance.
An empty comparison set imposes no requirements and is feasible. The proposed fixed target instance is also feasible: its single root variable can have local order \(1\succ 0\). Its in-degree is zero, so it belongs to every relevant \(\mathcal N_k\).
Changing the variable set in this branch is legitimate for a many-one reduction.
For a nonempty source instance, the target contains exactly the source’s ordered comparisons on the same variables. Its decision predicate depends only on those comparisons, not on their positive masses. Consequently, each candidate network is feasible for the source if and only if it is feasible for the target. Existential quantification over the same \(\mathcal N_k\) preserves both affirmative and negative answers.
The unchanged comparisons retain the bound of two differing variables. The unchanged feasible-network set also retains the in-degree-two solution property.
This establishes a polynomial-time many-one reduction from the cited NP-hard decision problem. The claimed NP-hardness follows, as does the conditional consequence that a polynomial-time algorithm would imply \(\mathrm P=\mathrm{NP}\). Membership in \(\mathrm{NP}\) is neither claimed nor needed.
No repair or additional clarification is required.
⟨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.