Answer: \(\mathrm{NP}\text{-complete}\)
Proposition 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateGiven a CA profile P and an integer k, decid- ing whether there exists d 2 D such that P i δ(d, Bi) k is NP-complete, even for binary variables and, for each voter, an acyclic dependency graph with maximal indegree 1.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given binary issues \(X_1,\ldots,X_p\), an explicit finite support of complete conditional approval ballot types \(B\) with acyclic dependency graphs of maximum indegree \(1\), rational masses \(\mu_B>0\) summing to \(1\), and a rational threshold \(q\), does there exist an outcome \(d\in\{0,1\}^p\) such that \(\sum_B \mu_B\delta(d,B)\le q\)?
There are \(m=p\ge 1\) binary issues \(X_1,\ldots,X_m\). A complete conditional approval ballot \(B\) specifies an acyclic directed graph \(G_B\) on the issues, with maximum indegree \(1\), and, for every issue \(X_i\) and every assignment \(u\) to its parents, an explicitly listed approval set \(a_{B,i}(u)\subseteq\{0,1\}\). Empty approval sets and approval of both values are allowed; different ballots may have different graphs.
A society is given by its support: the list of the \(\tau\) distinct ballot types with positive mass, each mass \(\mu_B\) a binary rational, with \(\sum_B\mu_B=1\). Here \(\tau\) is the support size, not the number of possible types. Let \(L\) be the total input bit length, including the ballots, masses, and threshold.
Every deterministic outcome \(d\in\{0,1\}^m\) is feasible. Define \(\delta(d,B)=|\{i:d_i\notin a_{B,i}(d_{\operatorname{Par}_{G_B}(X_i)})\}|\); a parentless issue has one unconditional approval set. Given \(q\in\mathbb{Q}\), decide whether some outcome satisfies \(\sum_B\mu_B\delta(d,B)\le q\).
Is this decision problem solvable in time polynomial in \(m,\tau,L\), or is it NP-hard?
For an explicitly listed finite electorate and an integer total-disagreement threshold, the corresponding decision problem is NP-complete even for binary issues and acyclic ballot graphs of maximum indegree \(1\).
For finite electorates with separable ballots (graphs with no edges) and unrestricted outcomes, conditional minisum winner determination is polynomial-time solvable.
The decision problem is \(\mathrm{NP}\)-complete. The hardness follows from the finite-electorate hardness stated in the question, even when every mass is a dyadic rational.
A certificate is an outcome \(d\in\{0,1\}^m\).
For each supported ballot \(B\) and issue \(X_i\), we read the value of its parent, if present, and consult the explicitly listed approval set. This determines \(\delta(d,B)\) using \(O(m)\) table lookups per ballot.
We can then compute and compare \(\sum_B\mu_B\delta(d,B)\) with \(q\) exactly in polynomial time. To justify the arithmetic bound, write \(\mu_B=a_B/b_B\) and \(q=c/e\), with positive denominators. The common denominator \(D=e\prod_B b_B\) has bit length at most the sum of the input denominator bit lengths, hence \(O(L)\). Multiplication by disagreement counts, which lie between \(0\) and \(m\), and summation over \(\tau\) terms increase the required bit length by at most \(O(\log m+\log\tau)\). Thus the verification uses polynomially many operations on integers of polynomial bit length.
Therefore the problem belongs to \(\mathrm{NP}\).
We use precisely the hardness premise supplied in the question: the corresponding problem for an explicitly listed finite electorate and an integer total-disagreement threshold is \(\mathrm{NP}\)-complete under the same ballot restrictions.
Let a source instance consist of ballots \(B_1,\ldots,B_n\), where \(n\geq 1\), and an integer threshold \(K\). Its question is whether some outcome \(d\) satisfies
\(\sum_{j=1}^{n}\delta(d,B_j)\leq K.\)
We construct a support instance as follows.
1. Add neutral ballots to obtain a power-of-two electorate size.
Set \(N=2^{\lceil\log_2 n\rceil}\). Let \(B^\circ\) have an edgeless graph and unconditional approval set \(\{0,1\}\) at every issue. This is a valid complete ballot, and \(\delta(d,B^\circ)=0\) for every outcome \(d\).
Append \(N-n\) copies of \(B^\circ\). This does not change total disagreement for any outcome. Moreover, \(n\leq N<2n\), so even explicitly performing this padding has polynomial cost.
2. Aggregate identical ballot types.
For each distinct type \(B\) in the padded electorate, let \(c_B\) be its multiplicity, and assign mass \(\mu_B=c_B/N\). List only types with \(c_B>0\).
These masses are positive and sum to \(1\). They are dyadic rationals because \(N\) is a power of two. Their numerators and denominators require \(O(\log n)\) bits each. Identical types can be identified in polynomial time by comparing their parent lists and approval tables in a canonical issue order.
The resulting support has size \(\tau\leq n+1\). All original ballot graphs retain their acyclicity and maximum indegree \(1\), and the added neutral ballot satisfies these restrictions as well.
3. Scale the threshold.
Set \(q=K/N\). For every outcome \(d\), the constructed instance satisfies
\(\sum_B\mu_B\delta(d,B)=\frac{1}{N}\sum_{j=1}^{n}\delta(d,B_j),\)
because aggregation preserves multiplicities and the added ballots contribute zero. Since \(N>0\), it follows that
\(\sum_B\mu_B\delta(d,B)\leq q\quad\Longleftrightarrow\quad\sum_{j=1}^{n}\delta(d,B_j)\leq K.\)
Thus the construction preserves both yes-instances and no-instances.
The construction and its output size are polynomial in the source input length: it retains at most \(n+1\) ballot types and adds only \(O(\log n)\) bits per mass and to the threshold denominator. Hence it is a polynomial-time many-one reduction, proving \(\mathrm{NP}\)-hardness.
Together, membership and hardness establish \(\mathrm{NP}\)-completeness. Consequently, an algorithm polynomial in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\). Specifying the society by its support does not remove the stated finite-electorate hardness.
⟨structured verdict parsed — rendered above⟩
The argument is correct and resolves the assigned problem: the support representation remains \(\mathrm{NP}\)-complete, including when all masses are dyadic rationals. No major or minor mathematical issues were found.
An outcome \(d\in\{0,1\}^m\) is a certificate of polynomial length. For each issue in each supported ballot, the explicitly listed approval table determines whether the chosen value is approved. Maximum indegree \(1\) ensures that at most one parent value must be read. Empty approval sets and approval of both values are handled by the same membership test. The stated \(O(m)\) table lookups per ballot are justified.
With positive denominators, the proposed \(D=e\prod_B b_B\) is a common denominator for every term and the threshold. Its bit length is \(O(L)\). Scaling numerators, multiplying by disagreement counts bounded by \(m\), and summing \(\tau\) terms require only polynomial bit length. Exact verification therefore runs in polynomial time, establishing membership in \(\mathrm{NP}\).
The prover states the source problem precisely: an explicitly listed electorate, the same ballot restrictions, and an integer threshold on total disagreement. This matches the hardness premise provided in USER_TASK. No additional external hardness theorem is assumed.
The ballot \(B^\circ\) is valid: its graph is edgeless, and approving both values is explicitly permitted. Its disagreement is zero for every outcome. Thus padding preserves total disagreement pointwise. For every \(n\geq1\), the chosen power of two satisfies \(n\leq N<2n\), including \(n=1\). The padding has polynomial size.
Multiplicities \(c_B>0\) produce positive masses \(c_B/N\) summing to \(1\). Because \(N\) is a power of two, the masses are dyadic. Their encodings have \(O(\log n)\) bits. Comparing parent lists and approval tables in a canonical issue order identifies identical ballot types in polynomial time. If the neutral ballot already appears in the original electorate, aggregation simply combines its copies. The bound \(\tau\leq n+1\) remains valid.
Original graphs remain unchanged, and the neutral graph satisfies all restrictions. The issue set and feasible deterministic outcomes are unchanged.
The displayed identity for weighted disagreement follows exactly from the multiplicities and zero contribution of neutral ballots. Since \(N>0\), comparison with \(q=K/N\) is equivalent to comparison of the original total disagreement with \(K\). This equivalence holds for every outcome and for arbitrary integer thresholds, including negative thresholds.
The output contains at most \(n+1\) explicitly represented types, polynomial-size masses, and a threshold whose numerator retains the original threshold’s bit length and whose denominator has \(O(\log n)\) bits. The construction is a polynomial-time many-one reduction. Together with membership, it establishes \(\mathrm{NP}\)-completeness. The stated implication that a polynomial-time algorithm would yield \(\mathrm{P}=\mathrm{NP}\) is justified.
No additional clarification or repair is needed.
⟨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.