Answer: Threshold decision is \(\mathrm{NP}\)-complete, even with \(\tau=1\), binary domains, nonnegative factors of arity at most three, fixed \(q=\tfrac12\), and a unique winner. Complete enumeration is polynomial in \(m,\tau,L,B\) if and only if \(\mathrm{P}=\mathrm{NP}\).
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateIf FCardinal is admissible, SC* chooses the set of winners according to the rule . Example. Consider three agents’ preferences over three binary do- main variables V = {A, B,C} depicted in Figure 1. The scoring func- tion fi of an agent i is defined by the position of the alternative in the preference ordering, i.e., the optimal outcome being at 1 and the worst outcome being at |X|.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite-domain variables \(V\), a finite outcome space \(X\), and \(\tau\) preference types with positive binary-rational masses \(\mu_t\) summing to \(1\), each with rational factorized cost \(f_t(x)=\sum_j \phi_{tj}(x|_{S_{tj}})\), compute the set of outcomes minimizing \(S_\mu(x)=\sum_t \mu_t f_t(x)\).
Let \(V=\{v_1,\ldots,v_m\}\) have explicitly listed, nonempty finite domains \(D_i\), and let \(X=\prod_{i=1}^m D_i\); there are no feasibility constraints.
A society is given by its support: the list of \(\tau\) types with positive binary-rational masses \(\mu_t\) satisfying \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Type \(t\) has cost \(f_t(x)=\sum_j\phi_{tj}(x|_{S_{tj}})\), where each scope \(S_{tj}\subseteq V\) is listed and each factor is an explicit table of signed rational values. Scopes may overlap and have arbitrary size.
Define \(S_\mu(x)=\sum_t\mu_t f_t(x)\) and the winner set \(W=\operatorname*{arg\,min}_{x\in X}S_\mu(x)\). All tied minimizers are winners; no strictness assumption or tie-breaking is imposed.
The required output is the explicit list \(W\). Let \(L\) be the total binary input length and \(B\) the output length; state running times in \(m,\tau,L,B\).
Can the complete winner set be computed in time polynomial in \(m,\tau,L,B\), or is the problem NP-hard already for deciding, given a binary-rational threshold \(q\), whether \(\min_{x\in X}S_\mu(x)\le q\)?
For finite agent lists, admissible best-first search returns all minimizers of a commutative, coordinatewise nondecreasing aggregation of cardinal costs; this is a correctness guarantee, without a polynomial running-time bound ([source](https://doi.org/10.3233/978-1-61499-098-7-528)). No complexity classification for the mass formulation is established by that guarantee.
The threshold decision problem is \(\mathrm{NP}\)-complete, already under all of the following restrictions:
Consequently, the complete winner set can be computed in time polynomial in \(m,\tau,L,B\) if and only if \(\mathrm{P}=\mathrm{NP}\). The singleton-winner restriction makes the enumeration hardness independent of potentially large output size.
For the decision problem, \(L\) includes the encoding of \(q\). All arithmetic below uses exact binary numerator/denominator representations.
Write each mass as \(\mu_t=a_t/b_t\), with \(b_t>0\), and each factor-table entry as \(c/d\), with \(d>0\). Let \(Q\) be the product of all mass denominators and all factor-table-entry denominators, including their separate occurrences.
The binary length of \(Q\) is \(O(L)\): the logarithm of a product is the sum of the logarithms of its factors, and these denominators are explicitly encoded in the input.
For every table entry belonging to type \(t\), the scaled weighted entry
\( A_{tj}(u)=Q\mu_t\phi_{tj}(u) \)
is an integer. Indeed, its denominator before cancellation is the product of that mass denominator and that entry denominator, which divides \(Q\). Consequently,
\( F(x):=Q S_\mu(x)=\sum_{t,j}A_{tj}(x|_{S_{tj}}) \)
is an integer for every assignment \(x\). All scaled entries and sums have polynomial binary length and can be computed in polynomial time.
A certificate for the threshold problem is an assignment \(x\in X\), specified by one domain-element index per coordinate. Its encoding has polynomial length because the domains are explicitly listed. The verifier checks domain membership, looks up the selected table entries, computes \(F(x)\), and compares it with \(Qq\) by exact rational arithmetic.
Thus the threshold problem belongs to \(\mathrm{NP}\).
We reduce from the standard \(\mathrm{NP}\)-complete problem of satisfiability for Boolean formulas in conjunctive normal form with at most three literals per clause.
Let the input formula be
\( \Phi=C_1\land\cdots\land C_k \)
on variables \(z_1,\ldots,z_n\). We may assume \(n\geq1\), adding an unused variable if necessary.
Set \(m=n\), \(D_i=\{0,1\}\), \(\tau=1\), and \(\mu_1=1\).
For each clause \(C_j\), let its scope contain precisely the variables appearing in that clause. Define its explicit table by
\( \psi_j(u)= \begin{cases} 0,&\text{if }u\text{ satisfies }C_j,\\ 1,&\text{otherwise}. \end{cases} \)
The scope has at most three variables, so its table has at most eight entries. Repeated variables in a clause cause no difficulty: the table evaluates the clause under assignments to its distinct variables.
Define
\( c(x)=\sum_{j=1}^{k}\psi_j(x|_{S_j}). \)
This is the nonnegative integer counting the clauses violated by \(x\).
For every variable \(z_i\), add the unary factor
\( \eta_i(0)=0,\qquad \eta_i(1)=2^{-(i+1)}. \)
The resulting social cost is
\( S_\mu(x)=c(x)+p(x),\qquad p(x)=\sum_{i=1}^{n}2^{-(i+1)}x_i. \)
The perturbation satisfies
\( 0\leq p(x)\leq\sum_{i=1}^{n}2^{-(i+1)} =\tfrac12-2^{-(n+1)}<\tfrac12. \)
Moreover,
\( 2^{n+1}p(x)=\sum_{i=1}^{n}2^{n-i}x_i. \)
The right-hand side is the integer represented by the binary string \(x_1\cdots x_n\). Therefore distinct assignments have distinct perturbation values.
Take distinct assignments \(x,y\).
If \(c(x)=c(y)\), then \(p(x)\neq p(y)\), so \(S_\mu(x)\neq S_\mu(y)\).
If \(c(x)\neq c(y)\), then
\( |c(x)-c(y)|\geq1 \quad\text{and}\quad |p(x)-p(y)|<\tfrac12. \)
Hence these differences cannot cancel, and again \(S_\mu(x)\neq S_\mu(y)\).
Thus all assignment costs are distinct. Since \(X\) is finite and nonempty, there is exactly one winner.
Use the fixed threshold \(q=\tfrac12\).
If \(\Phi\) is satisfiable, some assignment has \(c(x)=0\), and therefore
\( S_\mu(x)=p(x)<\tfrac12. \)
If \(\Phi\) is unsatisfiable, every assignment has \(c(x)\geq1\), and therefore
\( S_\mu(x)=c(x)+p(x)\geq1>\tfrac12. \)
Consequently,
\( \Phi\text{ is satisfiable} \quad\Longleftrightarrow\quad \min_{x\in X}S_\mu(x)\leq\tfrac12. \)
The construction has polynomial size. Each clause contributes a constant-size table, and the denominator \(2^{i+1}\) has \(O(i)\) binary digits, so all unary perturbation tables together require \(O(n^2)\) bits. Scope indices contribute \(O(k\log(n+1))\) bits.
This proves the asserted restricted \(\mathrm{NP}\)-hardness. Together with membership, it proves \(\mathrm{NP}\)-completeness.
Suppose an algorithm always outputs the explicit list \(W\) in time polynomial in \(m,\tau,L,B\).
Apply it to the reduction above. Every constructed instance has one winner, whose explicit binary assignment has output length \(B=O(n)\). Also, \(m=n\), \(\tau=1\), and \(L\) is polynomial in the formula length. The enumeration algorithm therefore runs in polynomial time on these instances.
Evaluate the returned winner’s cost and compare it with \(\tfrac12\). Section 3 shows that this decides satisfiability in polynomial time. Hence \(\mathrm{P}=\mathrm{NP}\).
This argument does not assume that arbitrary instances have few winners; it establishes hardness on instances whose output is always small.
Assume \(\mathrm{P}=\mathrm{NP}\). Use the integer-scaled objective \(F\) from Section 2, and compute
\( M=\sum_{t,j}\max_u |A_{tj}(u)|. \)
Every assignment satisfies \(|F(x)|\leq M\). The integer \(M\) has \(O(L)\) bits: each scaled entry has \(O(L)\) bits, and there are at most \(O(L)\) factors.
The predicate
\( \exists x\in X:\ F(x)\leq r \)
belongs to \(\mathrm{NP}\), by the verifier already described. Under the assumption \(\mathrm{P}=\mathrm{NP}\), it is decidable in polynomial time. Binary search over the integer interval \([-M,M]\) therefore finds
\( a^*=\min_{x\in X}F(x) \)
using \(O(L)\) predicate evaluations.
Now consider a prefix \(u=(x_1,\ldots,x_\ell)\). The predicate
\( \exists x\in X:\ x\text{ extends }u \text{ and }F(x)=a^* \)
also belongs to \(\mathrm{NP}\): a full extension is a certificate, and both conditions are polynomially checkable.
Starting with the empty prefix, perform a depth-first traversal. For each prefix that has a winning extension, test every value in the next coordinate’s domain. Recurse precisely on children that have a winning extension. At depth \(m\), output the assignment.
Every output has objective value \(a^*\). Conversely, every winner passes all tests along its sequence of prefixes and is therefore output exactly once. Thus all ties are retained.
Let \(K=|W|\) and \(d_{\max}=\max_i|D_i|\). There are at most \(1+mK\) prefixes having winning extensions: each such prefix lies on the path of at least one winner. Consequently, the traversal uses at most
\( d_{\max}(1+mK) \)
extension tests.
Because the domains are explicitly listed, \(d_{\max}\leq O(L)\). Under an ordinary explicit-list encoding, \(K\leq O(B+1)\). Thus, for some polynomial \(p\), the total running time is bounded by
\( O\!\left((L+mL(B+1))\,p(m,\tau,L)+B\right). \)
This is polynomial in \(m,\tau,L,B\). If \(m=0\), the product contains only the empty assignment, which can be output directly.
Without assuming \(\mathrm{P}=\mathrm{NP}\), exhaustive enumeration gives the bound
\( O\!\left( \left(\prod_{i=1}^{m}|D_i|\right) \operatorname{poly}(m,\tau,L)+B \right). \)
One pass determines the exact minimum, and a second pass outputs every assignment attaining it. This handles signed rational factors and arbitrary ties, but need not be output-polynomial.
The cited work describes a heuristic search framework with a winner-selection guarantee for cardinal preferences. [Li and Vo, *Choosing Combinatorial Social Choice by Heuristic Search*](https://research.monash.edu/en/publications/choosing-combinatorial-social-choice-by-heuristic-search)
That correctness guarantee is compatible with the classification proved here. Already for one supported type and nonnegative costs, a correct algorithm must solve the reduction above; an output-polynomial worst-case bound would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The threshold problem is \(\mathrm{NP}\)-complete, with hardness already on the stated instances having exactly one winner. The equivalence between output-polynomial enumeration and \(\mathrm{P}=\mathrm{NP}\) is also established. No major or minor mathematical issues were found.
1. Exact arithmetic and membership in \(\mathrm{NP}\)
The denominator construction is valid. Because \(Q\) includes separately every mass denominator and every table-entry denominator, the product \(b_t d\) divides \(Q\) for each weighted entry. Thus every \(A_{tj}(u)\) and every \(F(x)\) is an integer. Repeated denominator values do not invalidate divisibility: their occurrences are included separately.
The bit-length bounds are correct. The logarithm of \(Q\) is bounded by the total input length. Multiplication by the explicitly encoded numerators preserves an \(O(L)\) bound for each scaled entry, and summing at most \(O(L)\) selected entries still gives polynomial bit length. Signed entries cause no difficulty.
An assignment specified by domain-element indices has polynomial encoding length. Explicit tables permit polynomial-time lookup, and comparison with \(Qq\) uses exact rational arithmetic. The denominator of \(q\) need not divide \(Q\), since the comparison is not claimed to be an integer comparison. Membership in \(\mathrm{NP}\) follows.
2. Reduction and its encoding
The cited source problem is stated sufficiently precisely: satisfiability of Boolean CNF formulas with at most three literals per clause. It is the standard \(\mathrm{NP}\)-complete problem needed here.
The construction satisfies every claimed input restriction. It uses one supported type of mass one, binary domains, clause factors of arity at most three, and unary perturbations. Every entry is a nonnegative dyadic rational.
Each clause table correctly records whether the clause is violated. Taking the scope to contain distinct occurring variables handles repeated literals and repeated variables. Tautological clauses contribute zero everywhere; an empty clause, if allowed in the source convention, contributes the constant one. These cases do not break the reduction.
The construction is polynomial in size. Clause tables have at most eight entries. Encoding the unary denominator \(2^{i+1}\) requires \(O(i)\) bits, giving \(O(n^2)\) bits in total. The scope-index bound is also valid.
3. Perturbation and uniqueness
Both critical calculations are correct:
\[ \sum_{i=1}^{n}2^{-(i+1)}=\frac12-2^{-(n+1)} \]
and
\[ 2^{n+1}p(x)=\sum_{i=1}^{n}2^{n-i}x_i. \]
The latter expression is injective on binary assignments of fixed length \(n\). Therefore equal clause-violation counts give different total costs for distinct assignments.
For different clause-violation counts, the integer difference has absolute value at least one, whereas the perturbation difference has absolute value less than one-half. Cancellation is impossible.
Consequently, every constructed instance has pairwise distinct assignment costs and exactly one winner. This holds for both satisfiable and unsatisfiable formulas; uniqueness does not rely on unique satisfiability.
4. Threshold equivalence
For a satisfiable formula, a satisfying assignment has cost strictly below one-half. For an unsatisfiable formula, every assignment has cost at least one. Hence the claimed equivalence with the non-strict threshold \(q=\tfrac12\) is exact.
Together with the membership argument, this establishes \(\mathrm{NP}\)-completeness of the general threshold problem and \(\mathrm{NP}\)-hardness even when restricted to the constructed singleton-winner instances. The winner restriction is properly used as a guarantee on reduction outputs; the proof does not need an algorithm for recognizing uniqueness.
5. Enumeration hardness
The singleton-winner argument correctly addresses the output-size issue. Each reduction output has \(B=O(n)\) under the stated binary assignment encoding. An algorithm polynomial in \(m,\tau,L,B\) therefore runs in polynomial time on these instances.
Evaluating its returned winner and comparing its cost with one-half decides the source satisfiability problem. Thus output-polynomial enumeration implies \(\mathrm{P}=\mathrm{NP}\). This conclusion does not depend on the number of winners in arbitrary instances.
6. Enumeration assuming \(\mathrm{P}=\mathrm{NP}\)
The bound \(|F(x)|\leq M\) follows directly from the definition of \(M\). Its \(O(L)\) bit length is justified by the scaled-entry bounds and the explicitly encoded number of factors.
The integer threshold predicate belongs to \(\mathrm{NP}\), including for negative thresholds. Binary search therefore finds the minimum with \(O(L)\) polynomial-time predicate evaluations under the stated assumption. The case \(M=0\) presents no difficulty.
The prefix-extension predicate also belongs to \(\mathrm{NP}\): a full assignment certifies both the prefix constraint and equality to \(a^*\). Its parameters have polynomial encoding length.
The traversal outputs exactly the assignments attaining \(a^*\). Every winner has all its prefixes accepted, and every reported leaf satisfies the optimality test. Distinct traversal paths produce distinct assignments, so there are no duplicates and no lost ties.
The bound of \(1+mK\) accepted prefixes is valid, as is the resulting bound on extension tests. Explicit domains give \(d_{\max}=O(L)\), and ordinary explicit-list encoding gives \(K=O(B+1)\). The stated running-time expression is therefore polynomial in all four requested parameters. The separate treatment of \(m=0\) covers the empty-product case.
7. Unconditional bound and cited guarantee
The two-pass exhaustive algorithm correctly handles signed factors and all ties, with the stated running time.
Section 5 uses the search guarantee only for context. The [linked publication abstract](https://research.monash.edu/en/publications/choosing-combinatorial-social-choice-by-heuristic-search) supports the stated cardinal-winner guarantee. No complexity conclusion in the proof depends on that external guarantee.
Required clarification or repair: None.
⟨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.