Answer: \(\mathrm{NP}\)-complete, and hence \(\mathrm{NP}\)-hard.
Theorem 1 — class: hardness
Given \(m\) alternatives and a distribution \(\mu\) with positive binary-rational masses summing to \(1\) over supported ordered-pair comparison types \(r=(a\succ b)\), decide whether there are shared attribute sets \(H(a)\subseteq[3]\) for each alternative and care sets \(Q(r)\subseteq[3]\) for each supported type such that \(|H(a)\cap Q(r)|\ge |H(b)\cap Q(r)|+1\) for every \(r=(a\succ b)\) in the support.
Let \(A\) be a set of \(m\geq 2\) alternatives. A society is given by its support \(R\): a list of \(\tau\) distinct types \(r=(a\succ b)\), with \(a,b\in A\) and \(a\neq b\), each having a positive binary-rational mass \(\mu(r)\), where \(\sum_{r\in R}\mu(r)=1\). Here \(\tau\) is the support size, not the number of possible types.
The attribute universe is \(\{1,2,3\}\). Choose a shared Boolean attribute set \(H(a)\subseteq\{1,2,3\}\) for each alternative and a Boolean care set \(Q(r)\subseteq\{1,2,3\}\) for each supported type; empty sets and unused attributes are allowed.
Feasibility requires \(|H(a)\cap Q(r)|\geq |H(b)\cap Q(r)|+1\) for every \(r=(a\succ b)\in R\). Each type specifies only this comparison; no condition is imposed on its scores for other alternatives. Every supported type must be satisfied, regardless of its mass.
Let \(L\) be the total binary input length. State running times in \(m\), \(\tau\), and \(L\); the attribute bound is fixed at \(3\).
Is this distribution-over-types feasibility problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finite lists of voters, Boolean attribute model feasibility is NP-complete, and remains NP-hard with exactly three available attributes and every voter ranking exactly two alternatives. No separate complexity result for the distribution-over-types formulation is supplied.
The problem is \(\mathrm{NP}\)-complete, and hence \(\mathrm{NP}\)-hard. The stated finite-list hardness result transfers to distinct supported types by removing duplicates and assigning positive dyadic masses.
Feasibility depends only on the supported comparisons. Fix an attribute assignment \(H\). For a comparison \(r=(a\succ b)\), a suitable care set exists if and only if
\(H(a)\setminus H(b)\neq\varnothing\).
Indeed, for any care set \(Q\), the score difference is
\[
|H(a)\cap Q|-|H(b)\cap Q|
=
|(H(a)\setminus H(b))\cap Q|
-
|(H(b)\setminus H(a))\cap Q|.
\]
If \(H(a)\subseteq H(b)\), this difference is nonpositive, so the required inequality is impossible. Conversely, if \(j\in H(a)\setminus H(b)\), choosing \(Q=\{j\}\) makes the difference exactly \(1\).
Thus an instance is feasible precisely when there is an assignment \(H\) satisfying \(H(a)\setminus H(b)\neq\varnothing\) for every supported comparison. Neither its multiplicity nor its positive mass affects this condition.
Reduction from the supplied hard problem. Consider an instance of the stated \(\mathrm{NP}\)-hard finite-list problem with exactly three available attributes and each voter ranking exactly two alternatives. Write \(n\) for its number of voters and \(N\) for its binary input length. Each voter supplies one comparison \(a\succ b\).
Remove duplicate comparisons, obtaining a support \(R=\{r_1,\ldots,r_\tau\}\), where \(\tau\leq n\). Preserve the alternatives and the three available attributes.
For \(\tau\geq1\), let \(k=\lceil\log_2\tau\rceil\) and \(D=2^k\). Assign
\[
\mu(r_i)=\frac1D\quad(1\leq i<\tau),
\qquad
\mu(r_\tau)=\frac{D-\tau+1}{D}.
\]
Because \(D\geq\tau\), every mass is positive. Their sum is
\[
\frac{\tau-1+D-\tau+1}{D}=1.
\]
These are dyadic rationals, so the construction works even if “binary-rational” is interpreted as requiring a finite binary expansion. Each mass has encoding length \(O(1+\log\tau)\).
For any fixed \(H\), every original voter can be satisfied exactly when every distinct comparison in \(R\) can be satisfied, by the characterization proved above. Consequently, the original instance is feasible if and only if the constructed distribution instance is feasible. This establishes both directions of the reduction; duplicate voters introduce no additional requirement because their care sets are independent.
If the source instance has no voters, it is feasible and can be mapped to the fixed feasible instance consisting of two alternatives, one comparison, and mass \(1\).
Duplicate removal can be implemented in \(O(N^2)\) bit operations by direct comparisons of encoded pairs. The output length \(L\) satisfies
\(L=O(N+\tau\log(\tau+1))\), so the entire reduction is polynomial.
Membership and running times. A certificate need only specify the three membership bits of \(H(a)\) for each alternative appearing in the support. There are at most \(\min(m,2\tau)\) such alternatives; all other alternatives may receive the empty set.
The verifier checks \(H(a)\setminus H(b)\neq\varnothing\) for each supported pair. On promised valid inputs, an indexed implementation takes \(O(L+m+\tau)\) time, including input reading and initialization. Using only the supported alternatives gives a straightforward bit implementation taking \(O((L+\tau)^2)\) time and a certificate of length \(O(L+\tau)\). Hence verification is polynomial in the binary input length.
For completeness, enumerating the eight possible attribute sets for each alternative gives a deterministic decision algorithm taking \(O(L+8^m(m+\tau))\) time. The reduction proves that a polynomial-time decision algorithm would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The argument correctly establishes NP-completeness, using the finite-list hardness result supplied in the task. No major or minor mathematical gaps were found.
For fixed \(H\), the displayed identity for the score difference is correct: attributes in \(H(a)\cap H(b)\cap Q\) contribute equally and cancel.
Both directions of the claimed equivalence are valid:
Thus feasibility for this comparison is exactly \(H(a)\setminus H(b)\neq\varnothing\). This uses the task’s permission to choose a separate care set for each type and its stipulation that no other comparisons constrain that care set.
The duplicate-removal argument is sound.
For a fixed shared assignment \(H\), voters with the same comparison impose identical existence conditions on their independently chosen care sets. Removing duplicate comparisons therefore preserves feasibility in both directions. In particular, a satisfying care set for a supported comparison can also be assigned to every original voter having that comparison.
The reduction preserves the alternatives and the availability of exactly three attributes. It applies to precisely the restricted finite-list problem whose NP-hardness the task supplies. No additional hardness theorem is needed.
For \(\tau\geq1\), the definitions give \(\tau\leq D<2\tau\). Consequently, every numerator is positive, and the final numerator satisfies \(1\leq D-\tau+1\leq D\).
The normalization calculation is correct. All masses are dyadic rationals, and their numerators and denominators have \(O(1+\log\tau)\) bits. The construction therefore satisfies either the general rational interpretation or the finite-binary-expansion interpretation of “binary-rational.”
The case \(\tau=1\) is covered: \(k=0\), \(D=1\), and the unique mass is \(1\).
The separately handled source instance with no voters is feasible, and the proposed fixed target instance is feasible. That branch correctly preserves the answer while producing a nonempty normalized support.
The bound \(\tau\leq n\) is immediate from duplicate removal.
The claimed \(O(N^2)\) bound for direct duplicate checking is a valid coarse bit-operation bound: comparing all pairs of explicitly encoded records costs at most quadratic time in their total encoded length.
Preserving the original alternatives and retaining only distinct comparisons costs \(O(N)\) output space before masses. Adding the masses costs \(O(\tau\log(\tau+1))\) bits. Hence the stated output-length bound and polynomial reduction claim are justified.
The certificate is sufficient. Only alternatives occurring in supported comparisons need assigned membership bits; there are at most \(\min(m,2\tau)\) such alternatives. Assigning the empty set to all remaining alternatives cannot affect any constraint.
For each supported pair, the verifier checks whether at least one of the three attributes belongs to \(H(a)\) but not \(H(b)\). By the proved characterization, these checks are necessary and sufficient; explicit care sets need not be included.
The indexed running time is valid under the usual indexed implementation model. The separately stated polynomial bit implementation establishes NP membership even without that indexing assumption. The certificate-length bound is also valid.
Because the task promises valid normalized positive masses, feasibility verification need not establish those input promises.
There are eight possible attribute sets per alternative, giving \(8^m\) assignments. Checking each assignment takes \(O(m+\tau)\) indexed operations, so the stated exhaustive-search bound is correct under the same implementation convention.
The polynomial reduction establishes NP-hardness, and the certificate argument establishes membership in NP. Therefore the NP-completeness conclusion follows. The final implication concerning \(\mathrm{P}=\mathrm{NP}\) is also correct.
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.