Answer: \(\mathrm{NP}\)-complete, even for support size \(\tau=2\) and quota \(q=1\).
Theorem 10 — class: hardness
Given \(d\) issue variables, a finite support of \(\tau\) types \(\theta\) with rational masses \(\mu_\theta\) summing to \(1\), rational preference vectors \(p_\theta\), rational thresholds \(k_\theta\), and a rational quota \(q\), does there exist a world \(\omega:X\to\{-1,1\}\) such that \(\sum_{\theta:\,u_\theta(\omega)\ge k_\theta}\mu_\theta\ge q\), where \(u_\theta(\omega)=\sum_i p_\theta(x_i)\omega(x_i)\)? Equivalently, does there exist a satisfiable campaign theory under which at least a \(q\)-fraction of society meets its pessimistic utility threshold?
Let \(X=\{x_1,\ldots,x_d\}\), with \(d\ge1\), and write \(m=d\) for the number of issues. A society is given by its support: a list of \(\tau\ge1\) types with positive binary-rational masses \(\mu_\theta\) summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
Each type has rational preferences \(p_\theta:X\to[-1,1]\) and an arbitrary rational threshold \(k_\theta\). The quota is a rational \(q\in[0,1]\). Let \(L\) be the total binary input length.
A world is \(\omega:X\to\{-1,1\}\), with utility \(u_\theta(\omega)=\sum_{i=1}^{d}p_\theta(x_i)\omega(x_i)\). The decision problem asks whether some world satisfies \(\sum_{\theta:u_\theta(\omega)\ge k_\theta}\mu_\theta\ge q\).
Equivalently, a campaign theory is any satisfiable finite set of propositional formulas over \(X\), with no pre-existing commitments; its pessimistic utility is \(ut_\theta(T)=\min_{\omega\models T}u_\theta(\omega)\). The question is whether some such theory gives mass at least \(q\) utility at least its respective thresholds.
Is this decision problem solvable in polynomial time, or is it \(\mathrm{NP}\)-hard? State running times in \(m\), \(\tau\), and \(L\).
For a finite list of pessimistic voters, deciding whether some satisfiable campaign theory makes at least a specified integer number of voters meet their respective thresholds is \(\mathrm{NP}\)-complete.
The decision problem is \(\mathrm{NP}\)-complete. Hardness holds even when the quota is \(q=1\), and even when the support size is fixed at \(\tau=2\).
An exact algorithm runs in \(O(m\tau L^2+2^m m\tau L)\) bit operations. Thus fixed \(m\) gives polynomial time, whereas fixed \(\tau\) does not suffice unless \(\mathrm{P}=\mathrm{NP}\).
Suppose a satisfiable campaign theory \(T\) meets the thresholds of a set \(A\) of types whose total mass is at least \(q\). Choose any world \(\omega\models T\). For every \(\theta\in A\),
\(\displaystyle u_\theta(\omega)\ge \min_{\omega'\models T}u_\theta(\omega')=ut_\theta(T)\ge k_\theta.\)
Consequently, this world meets the thresholds of mass at least \(q\).
Conversely, given a world \(\omega\), let \(T_\omega\) contain the literal \(x_i\) when \(\omega(x_i)=1\), and the literal \(\neg x_i\) when \(\omega(x_i)=-1\). This theory is satisfiable and has exactly one model, namely \(\omega\). Hence \(ut_\theta(T_\omega)=u_\theta(\omega)\) for every type.
Therefore the two existential decision problems are identical. In particular, allowing arbitrary finite campaign theories does not require a larger certificate than a single world.
A certificate consists of the \(m\) signs describing a world. Its validity can be checked using exact integer arithmetic.
Write each preference as \(p_\theta(x_i)=a_{\theta i}/b_{\theta i}\), and write \(k_\theta=c_\theta/e_\theta\), with positive denominators. Define
\(\displaystyle D_\theta=e_\theta\prod_{i=1}^{m}b_{\theta i},\qquad A_{\theta i}=D_\theta p_\theta(x_i),\qquad K_\theta=D_\theta k_\theta.\)
These are integers, and \(D_\theta>0\). Thus a type meets its threshold precisely when
\(\displaystyle \sum_{i=1}^{m}A_{\theta i}\omega(x_i)\ge K_\theta.\)
Similarly, choose a positive common denominator \(E\) for all masses and the quota, and define the integers \(B_\theta=E\mu_\theta\) and \(Q=Eq\). The quota condition becomes
\(\displaystyle \sum_{\theta:\,\sum_i A_{\theta i}\omega(x_i)\ge K_\theta}B_\theta\ge Q.\)
The products of denominators have \(O(L)\) bits: the bit length of a product is bounded by the sum of its factors’ bit lengths, which is bounded by the input length. The scaled integers and their utility sums also have \(O(L)\) bits; summing \(m\) terms adds at most \(O(\log m)\) bits.
Using schoolbook multiplication and division, preprocessing takes \(O(m\tau L^2)\) bit operations. Thereafter, checking one world takes \(O(m\tau L)\) bit operations. This proves membership in \(\mathrm{NP}\).
Enumerating all \(2^m\) worlds gives the exact bound
\(\displaystyle O(m\tau L^2+2^m m\tau L).\)
We reduce from \(3\)-SAT, using its standard \(\mathrm{NP}\)-completeness.
First simplify the input formula by removing tautological clauses, repeated literals within clauses, and duplicate clauses. These operations preserve satisfiability. If no clauses remain, output a fixed yes-instance: one issue, one type with zero preference and threshold zero, mass one, and quota one.
Otherwise, let the remaining clauses be \(C_1,\ldots,C_c\). Each clause has \(r_j\in\{1,2,3\}\) literals on distinct variables.
Use one issue for each variable. Interpret \(\omega(x_i)=1\) as assigning that variable true. For clause \(C_j\), introduce a type with preferences
\(\displaystyle p_j(x_i)= \begin{cases} 1,&\text{if }x_i\text{ occurs positively in }C_j,\\ -1,&\text{if }x_i\text{ occurs negatively in }C_j,\\ 0,&\text{if }x_i\text{ does not occur in }C_j, \end{cases} \qquad k_j=2-r_j.\)
Every satisfied literal contributes \(1\) to this type’s utility, and every unsatisfied literal contributes \(-1\). If precisely \(s_j\) literals are satisfied, then
\(\displaystyle u_j(\omega)=s_j-(r_j-s_j)=2s_j-r_j.\)
It follows that
\(\displaystyle u_j(\omega)\ge k_j \quad\Longleftrightarrow\quad 2s_j-r_j\ge 2-r_j \quad\Longleftrightarrow\quad s_j\ge1.\)
Thus the type meets its threshold exactly when its clause is satisfied.
To obtain valid binary-rational masses, put \(B=2^{\lceil\log_2 c\rceil}\), and assign
\(\displaystyle \mu_j=\frac1B\quad(1\le j<c),\qquad \mu_c=\frac{B-c+1}{B}.\)
Every mass is positive and dyadic, and their sum is one. Set \(q=1\). Because every type has positive mass, a world achieves this quota exactly when every type meets its threshold. By the preceding calculation, this occurs exactly when the original formula is satisfiable.
The construction has \(m\) issues and \(\tau=c\) types. Its dense preference table has \(mc\) entries, and each mass requires \(O(\log(c+1))\) bits. Its encoding length is therefore polynomial in the source input length. Removing duplicate clauses ensures that the constructed types are distinct, so \(\tau\) is genuinely the support size.
This proves \(\mathrm{NP}\)-hardness under all stated input restrictions. Together with Section 2, it proves \(\mathrm{NP}\)-completeness.
A separate reduction from the standard \(\mathrm{NP}\)-complete problem PARTITION establishes this stronger restriction.
Given positive binary-encoded integers \(a_1,\ldots,a_m\), choose a power of two \(D\ge\max_i a_i\). Construct two types with
\(\displaystyle p_1(x_i)=\frac{a_i}{D},\qquad p_2(x_i)=-\frac{a_i}{D},\qquad k_1=k_2=0,\qquad \mu_1=\mu_2=\frac12,\qquad q=1.\)
The preferences lie in \([-1,1]\); indeed, they are dyadic. The encoding length of \(D\), and hence of the whole construction, is polynomial in the PARTITION input length.
The two utilities satisfy \(u_2(\omega)=-u_1(\omega)\). Quota one therefore requires
\(\displaystyle u_1(\omega)\ge0\quad\text{and}\quad -u_1(\omega)\ge0,\)
which is equivalent to
\(\displaystyle \sum_{i=1}^{m}a_i\omega(x_i)=0.\)
For \(S=\{i:\omega(x_i)=1\}\), this equation is equivalent to
\(\displaystyle \sum_{i\in S}a_i=\sum_{i\notin S}a_i.\)
Thus the constructed instance is yes exactly when the PARTITION instance is yes. This proves \(\mathrm{NP}\)-completeness for the restriction \(\tau=2\). This particular reduction establishes ordinary, rather than strong, hardness.
When \(\tau=1\), the single type has mass one. If \(q=0\), every world succeeds. If \(q>0\), success is equivalent to that type meeting its threshold. Since the signs can be chosen independently,
\(\displaystyle \max_{\omega}u_1(\omega)=\sum_{i=1}^{m}|p_1(x_i)|.\)
Consequently, this case is decided by comparing that sum with \(k_1\), in \(O(mL^2)\) bit operations using exact arithmetic.
The established running-time consequences are:
⟨structured verdict parsed — rendered above⟩
The argument is correct in substance and resolves the intended decision problem. It establishes \(\mathrm{NP}\)-completeness, including the restriction \(\tau=2\) and \(q=1\). The stated running times are valid under the intended efficient choices of scaling denominators.
There are two minor omissions: the choices of \(E\) and \(D\) should explicitly satisfy the encoding-length bounds used later. Neither omission requires new mathematics.
Both directions are valid.
The argument preserves the qualifying mass in both directions. It also covers \(q=0\). Since \(m\ge1\), worlds exist, and the construction of a singleton-model theory is valid.
The conclusion that a world suffices as a certificate is justified; no bound on the size of arbitrary campaign theories is needed.
The preference and threshold scaling is correct. Each denominator \(b_{\theta i}\) and \(e_\theta\) divides \(D_\theta\), so \(A_{\theta i}\) and \(K_\theta\) are integers. Multiplication by positive \(D_\theta\) preserves the threshold inequality, including for negative preferences or thresholds.
The bit-length argument is sound:
The same reasoning supports the mass comparison when \(E\) is chosen with \(O(L)\) bits.
Minor issue — the choice of \(E\). The instruction to “choose a positive common denominator” does not explicitly impose a size bound. Common denominators can be arbitrarily large, whereas the subsequent arithmetic bounds require \(E\) to have \(O(L)\) bits. The later reference to products of denominators makes the intended construction apparent.
Minimum clarification: specify the common-denominator construction used for \(E\), or explicitly require its bit length to be \(O(L)\).
With that clarification, schoolbook arithmetic supports preprocessing time \(O(m\tau L^2)\). Each world then requires \(O(m\tau L)\) bit operations for utility and mass comparisons. The certificate has \(m\) signs, so verification is polynomial in the input length.
Enumerating all worlds consequently gives the claimed bound
\[
\text{ }
\]
\(O(m\tau L^2+2^m m\tau L)\).
The reduction is correct.
The cited source problem is the standard \(\mathrm{NP}\)-complete Boolean \(3\)-SAT problem. Removing tautological clauses, repeated literals, and duplicate clauses preserves satisfiability. For the standard source problem, this leaves nonempty clauses of sizes in \(\{1,2,3\}\), unless all clauses disappear. The fixed yes-instance correctly handles that latter case and satisfies \(m\ge1\) and \(\tau\ge1\).
The preferences correctly encode literal truth: every satisfied literal contributes \(1\), and every unsatisfied literal contributes \(-1\). The computation
\(u_j(\omega)=2s_j-r_j\)
is correct, and comparison with \(k_j=2-r_j\) is equivalent to \(s_j\ge1\), including for clauses of sizes one and two.
The mass construction satisfies every restriction:
At quota one, positive masses force every type to qualify. Hence the constructed instance is satisfiable exactly when the source formula is satisfiable.
The dense table has polynomial size. Distinct simplified clauses yield distinct preference vectors, so removing duplicate clauses does ensure that the listed types form a support of size \(c\).
No substantive gap occurs in this reduction.
The source problem is the standard \(\mathrm{NP}\)-complete PARTITION problem on positive binary-encoded integers. The displayed equal-sum condition specifies its decision criterion.
The construction satisfies the target restrictions: preferences have absolute value at most one, thresholds are rational, masses are positive and sum to one, and the quota is one. The two types are distinct because the input integers are positive and \(m\ge1\).
The utility identity \(u_2(\omega)=-u_1(\omega)\) is correct. Requiring both utilities to be nonnegative is equivalent to \(u_1(\omega)=0\), and hence to the displayed signed-sum equation. The correspondence between positive signs and one part of an equal-sum partition is valid in both directions.
Minor issue — the choice of \(D\). Merely requiring a power of two \(D\ge\max_i a_i\) does not guarantee the later assertion that its encoding length is polynomial: arbitrarily large powers also satisfy that requirement. The intended efficiently bounded choice is routine.
Minimum clarification: specify a choice of \(D\) whose bit length is polynomial in the source input length.
With that clarification, the reduction proves hardness at \(\tau=2\), and the earlier membership argument establishes completeness for that restriction. The qualification that this reduction establishes ordinary rather than strong hardness is appropriate.
For \(\tau=1\), normalization forces the mass to be one. The separate treatment of \(q=0\) is correct. For \(q>0\), success requires the single type to qualify.
The maximization formula
\(\max_\omega u_1(\omega)=\sum_i|p_1(x_i)|\)
is justified by independent choices of signs, including when a preference is zero. The claimed \(O(mL^2)\) exact-arithmetic bound is valid.
The enumeration bound gives polynomial time when \(m\) is fixed. Hardness at \(\tau=2\) correctly shows that fixing support size alone does not ensure polynomial time unless \(\mathrm{P}=\mathrm{NP}\).
The proof addresses the explicitly defined world/campaign-theory decision problem. It makes no separate claim about an independently defined “continuous” variant; the requested complexity status below refers to the supplied target problem.
⟨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.