d4-conf-ecai-2014-0305 (d4-conf-ecai-2014-0305)

Given a finite object set \(H\), a query \(Q\), and supported preference-evidence profiles \(P_t\) with binary-rational masses \(\mu_t\) summing to \(1\), compute the exact expected fraction of the population whose sampled ranking satisfies \(Q\): \(\operatorname{Prev}_{\mu}(Q)=\sum_t\mu_t\frac{\sum_{\lambda\models Q}\exp(s_t(\lambda))}{\sum_{\lambda\in W}\exp(s_t(\lambda))}\), where \(s_t(\lambda)=\sum_{(F,w)\in P_t}w\,\mathbf{1}[\lambda\models F]\).

Let \(H\) be an explicitly listed set of \(m\geq1\) objects, and let \(W\) be its strict total rankings. Preference formulas are Boolean combinations of atoms \(a\succ b\), for distinct \(a,b\in H\); an atom holds exactly when \(a\) precedes \(b\).
A society is given by its support: the list of its \(\tau\) types with positive binary-rational masses \(\mu_t\) summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
Each type has a finite preference-evidence profile \(P_t\). A finite-weight entry is encoded as \((F,r)\), where \(r>0\) is binary rational and its log weight is \(\log r\); an infinite-weight entry is a hard formula that must hold. Let \(W_t\subseteq W\) satisfy all hard formulas, and require \(W_t\neq\varnothing\).
Define \(u_t(\lambda)=\prod_{(F,r)\in P_t:\,\lambda\models F}r\), using only finite-weight entries. Given a preference formula \(Q\), compute the exact rational value \(\operatorname{Prev}_{\mu}(Q)=\sum_{t=1}^{\tau}\mu_t\frac{\sum_{\lambda\in W_t:\,\lambda\models Q}u_t(\lambda)}{\sum_{\lambda\in W_t}u_t(\lambda)}\), encoded as a reduced binary fraction. Let \(L\) be the total input bit length, including all formulas and numerical data.
Is exact computation of \(\operatorname{Prev}_{\mu}(Q)\) possible in time polynomial in \(m,\tau,L\), or is it NP-hard?
For unrestricted real log weights, exact single-profile preference-query probability is \(\#\mathrm{P}\)-hard ([Probabilistic Preference Logic Networks](https://doi.org/10.3233/978-1-61499-419-0-561)). No separate continuous-side result has been verified.

Result

Exact computation is \(\mathrm{NP}\)-hard, even with one type, no evidence entries, and uniform probability over all strict rankings. More strongly, it is \(\#\mathrm{P}\)-hard under polynomial-time reductions that recover a counting answer from one exact probability.

Thus a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\). The proof uses no real-valued weights or continuous-side hardness result.

Reduction from Boolean satisfiability

Let \(\varphi(x_1,\ldots,x_n)\) be a Boolean CNF formula, with \(n\geq1\). Construct the following instance:

• The object set is \(H=\{a_1,b_1,\ldots,a_n,b_n\}\), so \(m=2n\).
• There is one type, with mass \(\mu_1=1\).
• Its evidence profile is empty. Consequently \(W_1=W\) and \(u_1(\lambda)=1\) for every ranking \(\lambda\).
• The query \(Q_\varphi\) is obtained from \(\varphi\) by replacing every variable \(x_i\) by the atom \(a_i\succ b_i\), preserving all Boolean connectives.

The construction has polynomial size and satisfies the required promise \(W_1\neq\varnothing\).

For each ranking \(\lambda\), define its induced assignment \(s(\lambda)\in\{0,1\}^n\) by
\(s_i(\lambda)=1\) exactly when \(a_i\) precedes \(b_i\).
By the semantics of Boolean connectives,
\(\lambda\models Q_\varphi\) if and only if \(s(\lambda)\models\varphi\).

Every assignment has equally many rankings

For an assignment \(s\in\{0,1\}^n\), let
\(R_s=\{\lambda\in W:s(\lambda)=s\}\).

Fix any two assignments \(s,t\). In a ranking, interchange the labels \(a_i\) and \(b_i\) precisely for those indices satisfying \(s_i\neq t_i\). This operation:

• reverses the relative order of \(a_i,b_i\) for each interchanged pair;
• preserves the relative order within every other designated pair; and
• is its own inverse.

It therefore gives a bijection from \(R_s\) to \(R_t\). All \(2^n\) sets \(R_s\) have equal cardinality. They partition the \((2n)!\) rankings, so each has cardinality \((2n)!/2^n\).

Writing \(\#\mathrm{SAT}(\varphi)\) for the number of satisfying assignments, we obtain
\(\lvert\{\lambda\in W:\lambda\models Q_\varphi\}\rvert =\#\mathrm{SAT}(\varphi)(2n)!/2^n\).
Hence the constructed instance satisfies the exact identity
\(\operatorname{Prev}_{\mu}(Q_\varphi)=\#\mathrm{SAT}(\varphi)/2^n\).

Consequences

The formula \(\varphi\) is satisfiable exactly when the returned probability is positive. For a reduced binary fraction, positivity can be checked directly from its numerator. A polynomial-time exact-probability algorithm would therefore decide Boolean satisfiability in polynomial time. This proves \(\mathrm{NP}\)-hardness.

Moreover, multiplying the exact output by \(2^n\) recovers \(\#\mathrm{SAT}(\varphi)\). This multiplication takes polynomial time: \(2^n\) has \(n+1\) binary digits, and the probability in this construction has a denominator dividing \(2^n\). Since counting satisfying assignments is \(\#\mathrm{P}\)-complete, the same reduction establishes the stronger counting hardness.

The exact output has polynomial length

The hardness above does not arise from an excessively long required output. In fact, every valid input in the question has a polynomial-length exact answer.

For type \(t\), write its finite rational weights as \(r_{tj}=p_{tj}/q_{tj}\), where \(p_{tj},q_{tj}\) are positive integers. Define
\(B_t=\prod_j q_{tj}\) and \(A_t=\prod_j\max(p_{tj},q_{tj})\), with empty products equal to \(1\).

For each ranking, the scaled weight is the positive integer
\(U_t(\lambda)=B_tu_t(\lambda) =\prod_{\lambda\models F_{tj}}p_{tj}\prod_{\lambda\not\models F_{tj}}q_{tj}\).
In particular, \(U_t(\lambda)\leq A_t\).

Let
\(Z_t=\sum_{\lambda\in W_t}U_t(\lambda)\) and
\(N_t=\sum_{\lambda\in W_t:\lambda\models Q}U_t(\lambda)\).
The nonemptiness promise and positivity of all weights imply
\(1\leq Z_t\leq m!A_t\), while \(0\leq N_t\leq Z_t\).
The profile’s query probability is exactly \(N_t/Z_t\).

Write \(\mu_t=a_t/b_t\), with positive integers \(a_t,b_t\). A common denominator for the society probability is
\(D=\prod_{t=1}^{\tau}(b_tZ_t)\).
Its bit length is bounded by
\(1+\sum_t\log_2 b_t+\tau\log_2(m!)+\sum_t\log_2 A_t =O(L+\tau m\log_2(m+1))\).
Here the logarithms of all input numerators and denominators sum to at most a constant multiple of their total encoding length.

Because the final probability lies between \(0\) and \(1\), its numerator over denominator \(D\) lies between \(0\) and \(D\). Reduction to lowest terms cannot increase either integer. Thus the requested output has polynomial bit length.

An exact counting-oracle upper bound

For completeness, the problem belongs to \(\mathrm{FP}^{\#\mathrm{P}}\).

To compute \(Z_t\) using a \(\#\mathrm{P}\) oracle, a nondeterministic polynomial-time machine guesses a ranking using a fixed-length encoding, rejecting codes that are not permutations or violate a hard formula. Every ranking has exactly one valid code.

For a valid ranking, the machine computes \(U_t(\lambda)\). Let
\(k_t=\sum_j\operatorname{bitlength}(\max(p_{tj},q_{tj}))\).
It then guesses a \(k_t\)-bit integer \(y\) and accepts precisely when \(y<U_t(\lambda)\). This produces exactly \(U_t(\lambda)\) accepting branches for that ranking. For an empty profile, \(k_t=0\), and the unique empty guess represents \(y=0\), producing one accepting branch.

All formula evaluations and integer products require polynomial time. Thus the total accepting count is \(Z_t\). Adding the requirement \(\lambda\models Q\) gives a machine whose accepting count is \(N_t\).

Two counting-oracle calls per type therefore provide all required integers. The polynomial bit-length bounds above allow the remaining rational arithmetic and reduction to lowest terms in polynomial time.

⟨structured verdict parsed — rendered above⟩

The output correctly resolves the task: exact computation is \(\mathrm{NP}\)-hard, even for one type with an empty evidence profile. The stronger counting-hardness claim, polynomial output-length bound, and \(\mathrm{FP}^{\#\mathrm{P}}\) upper bound are also justified. No major or minor mathematical issues were found.

1. Validity and size of the reduction

The constructed instance satisfies all requirements:

• The \(2n\) objects are distinct and explicitly listed.
• There is exactly one supported type, with positive rational mass \(1\).
• An empty evidence profile imposes no hard constraints and gives weight \(1\) to every ranking.
• The set of admissible rankings is nonempty.
• Substituting comparison atoms for Boolean variables produces a permitted preference formula of polynomial size.

The restriction to Boolean CNF formulas with \(n\geq1\) does not affect the standard satisfiability or counting-hardness results.

2. Query semantics

The induced assignment is well-defined because every strict total ranking orders each distinct pair \(a_i,b_i\) in exactly one direction.

The claimed equivalence
\[ \lambda\models Q_\varphi \quad\Longleftrightarrow\quad s(\lambda)\models\varphi \]
follows directly from the substitution and the semantics of Boolean connectives. It applies to negated literals as well as positive literals.

3. Equal cardinalities of assignment classes

The label-interchange operation is valid. The designated pairs are disjoint, so interchanging labels in one pair cannot alter the relative order within another designated pair.

For each index where \(s_i\neq t_i\), the operation reverses that pair’s induced Boolean value; it preserves all other induced values. It therefore maps \(R_s\) into \(R_t\). Applying the same operation again restores the original ranking, establishing a bijection.

Every ranking induces exactly one assignment, so the classes partition all \((2n)!\) rankings. Their equal cardinalities consequently give
\[ |R_s|=\frac{(2n)!}{2^n}. \]
This also establishes that every assignment is represented.

4. Probability identity and hardness

Summing the equal-sized classes associated with satisfying assignments gives the stated identity
\[ \operatorname{Prev}_{\mu}(Q_\varphi) =\frac{\#\mathrm{SAT}(\varphi)}{2^n}. \]

Thus satisfiability is equivalent to strict positivity of the returned probability. Positivity is decidable directly from the numerator of the required reduced fraction, including the unsatisfiable case, whose numerator is zero.

The invoked standard complexity results apply: Boolean CNF satisfiability is \(\mathrm{NP}\)-complete, and counting satisfying assignments of Boolean CNF formulas is \(\#\mathrm{P}\)-complete.

The stronger reduction is correctly qualified as recovering a counting answer from one exact probability. Multiplication by \(2^n\) recovers the count even when the probability has been reduced to lowest terms. The output numerator and denominator have \(O(n)\) bits, so this recovery takes polynomial time.

Accordingly, the implication that a polynomial-time exact algorithm would yield \(\mathrm{P}=\mathrm{NP}\) is justified. No hardness result concerning unrestricted real weights is needed.

5. Polynomial output length

The common-denominator scaling is correct:
\[ B_tu_t(\lambda) =\prod_{\lambda\models F_{tj}}p_{tj} \prod_{\lambda\not\models F_{tj}}q_{tj}. \]
Each evidence entry contributes exactly one factor, so this remains valid with repeated formulas or entries.

The scaled weight is a positive integer bounded by \(A_t\). Consequently,
\[ 1\leq Z_t\leq m!A_t, \qquad 0\leq N_t\leq Z_t. \]
The lower bound uses precisely the promised nonemptiness and positivity hypotheses.

Each society summand has denominator dividing \(b_tZ_t\), so the proposed product \(D\) is a valid common denominator. Its bit-length estimate follows from the input encoding lengths and the bound on \(Z_t\).

Because the masses sum to \(1\), the final probability lies in \([0,1]\). Its numerator over \(D\) is therefore an integer between \(0\) and \(D\). Reduction cannot increase either integer. The output-length conclusion follows, including when \(m=1\), profiles are empty, or the probability is zero.

6. Counting-oracle upper bound

The nondeterministic construction correctly counts scaled weights. A fixed-length permutation encoding can give exactly one valid code per ranking; invalid codes and rankings violating hard formulas are rejected.

For a nonempty finite profile, the definition of \(k_t\) ensures
\[ U_t(\lambda)\leq A_t<2^{k_t}. \]
There are therefore exactly \(U_t(\lambda)\) accepting guesses satisfying \(y<U_t(\lambda)\). For an empty finite profile, the explicitly handled zero-bit guess gives exactly one accepting branch.

Formula evaluation, integer multiplication, and comparison require polynomial time. Adding the query test correctly changes the count from \(Z_t\) to \(N_t\). The previously established bit-length bounds justify polynomial-time rational arithmetic after the oracle calls.

The claimed \(\mathrm{FP}^{\#\mathrm{P}}\) upper bound is sound.

No additional clarification or repair is required.

⟨structured verdict parsed — rendered above⟩