Answer: \(\mathrm{NP}\)-complete, even with positive dyadic masses; polynomial-time solvable in \(m,\tau,\ell,L\) if and only if \(\mathrm{P}=\mathrm{NP}\).
Theorem 3.1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateEGAL-DEC is NP-complete, even in the UP setting with λ = 1.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a project set \(P\), horizon \(\ell\), and a support of \(\tau\) UP approval-trajectory types \(\theta\), each with binary-rational mass \(\mu_\theta>0\) summing to \(1\), is there an outcome \(o\in P^\ell\) such that \(u_\theta(o)=\sum_{t=1}^{\ell}\mathbf{1}[o_t\in S_{\theta t}]\ge 1\) for every supported type? Here each \(S_{\theta t}\) is a singleton project approval set.
Let \(P\) be a project set with \(m\ge 1\), and let \(\ell\ge 1\) be an integer horizon.
A society is given by its support: a list of \(\tau\ge 1\) distinct approval-trajectory types \(\theta\), each with binary-rational mass \(\mu_\theta>0\), where \(\sum_\theta\mu_\theta=1\). Here \(\tau\) is the support size, not the number of possible types.
Each trajectory is explicitly listed as \((S_{\theta 1},\ldots,S_{\theta\ell})\), with every \(S_{\theta t}\subseteq P\) a singleton; this is the unique-preferences (UP) domain.
An outcome is a deterministic sequence \(o\in P^\ell\); projects may be repeated across timesteps. Define \(u_\theta(o)=\sum_{t=1}^{\ell}\mathbf{1}[o_t\in S_{\theta t}]\).
The decision problem asks whether an outcome exists with \(u_\theta(o)\ge 1\) for every supported type. Let \(L\) be the total binary input length; state running times in \(m,\tau,\ell,L\).
Is this decision problem solvable in polynomial time in \(m,\tau,\ell,L\), or is it NP-hard?
For a finite list of agents, deciding whether every agent can receive utility at least \(1\) is NP-complete even in the UP domain. [Source](https://arxiv.org/html/2408.13637v2#S3).
No separate classification for the distribution-over-types formulation is asserted here.
The problem is \(\mathrm{NP}\)-complete, even when all masses are positive dyadic rationals. Consequently, a polynomial-time algorithm in \(m,\tau,\ell,L\) exists if and only if \(\mathrm{P}=\mathrm{NP}\).
The key observation is that masses do not affect feasibility: the requirement applies separately to every supported trajectory.
Write \(S_{\theta t}=\{a_{\theta t}\}\), where \(a_{\theta t}\in P\). An outcome \(o\) satisfies type \(\theta\) precisely when there exists \(t\in\{1,\ldots,\ell\}\) with \(o_t=a_{\theta t}\).
A certificate is the sequence \(o\in P^\ell\). With projects indexed by integers, its length is \(O(\ell\log(m+1))\), which is polynomial in \(L\) because trajectories are explicitly listed and \(\tau\ge 1\).
The verifier checks that every chosen project belongs to \(P\), then checks the above condition for each supported type. This requires at most \(\tau\ell\) project comparisons. With binary project indices, verification takes \(O(L+\tau\ell\log(m+1))\) time using indexed storage. Thus the problem belongs to \(\mathrm{NP}\).
Theorem 3.1 of the cited paper establishes \(\mathrm{NP}\)-completeness for explicitly listed finite agents, with singleton approvals at every timestep and utility threshold \(1\). Its outcomes also choose one project per timestep and allow repetitions, so its feasibility condition matches ours. [Source: Theorem 3.1 and model definitions](https://arxiv.org/html/2408.13637v2#S3).
Consider such a finite-agent instance with \(n\ge 1\) agents. Keep its project set and horizon unchanged.
Construct distinct types. Partition the agents according to equality of their entire approval trajectories, and retain one trajectory from each class. Let the resulting support size be \(\tau\), so \(1\le\tau\le n\). The trajectories are distinct by construction, and every approval set remains a singleton.
Assign valid masses. Set \(q=\lceil\log_2\tau\rceil\), and number the retained types from \(1\) through \(\tau\). Define
\(\displaystyle \mu_j=\frac{1}{2^q}\quad(1\le j<\tau),\qquad \mu_\tau=\frac{2^q-\tau+1}{2^q}.\)
These are dyadic rationals. Since \(2^q\ge\tau\), every mass is positive. Their sum is
\(\displaystyle \sum_{j=1}^{\tau}\mu_j=\frac{\tau-1+2^q-\tau+1}{2^q}=1.\)
This also handles \(\tau=1\): then \(q=0\) and the sole mass is \(1\). Each mass requires \(O(\log(\tau+1))\) bits, so all masses together require \(O(\tau\log(\tau+1))\) bits.
Prove equivalence. For any outcome \(o\), an agent and the retained type representing its trajectory have exactly the same utility. Therefore,
\(\displaystyle \bigl[u_i(o)\ge1\text{ for every original agent }i\bigr]\quad\Longleftrightarrow\quad\bigl[u_\theta(o)\ge1\text{ for every retained type }\theta\bigr].\)
Thus the original instance is feasible exactly when the constructed support instance is feasible.
Check polynomial size and time. Let \(L_{\mathrm{fin}}\) be the original input length. Pairwise trajectory comparisons suffice to remove duplicates in time \(O(L_{\mathrm{fin}}+n^2\ell\log(m+1))\). Writing the masses adds \(O(n\log(n+1))\) time and bits. Since the finite-agent trajectories are explicitly listed, these bounds are polynomial in \(L_{\mathrm{fin}}\).
This is a polynomial many-one reduction from an \(\mathrm{NP}\)-complete problem, proving \(\mathrm{NP}\)-hardness. Together with membership, it proves \(\mathrm{NP}\)-completeness.
Enumerating all \(m^\ell\) outcomes and checking each gives a deterministic algorithm with running time \(O(L+m^\ell\tau\ell\log(m+1))\) using indexed storage. This bound is exponential in general; replacing agents by distinct supported types does not remove the hardness.
⟨structured verdict parsed — rendered above⟩
The output resolves the assigned problem correctly. The reduction preserves feasibility, produces a valid support of distinct types with positive dyadic masses, and has polynomial size and running time. No major or minor issues were found.
Theorem 3.1 states NP-completeness in the UP domain with threshold \(1\). The paper defines UP by singleton approvals at every timestep, outcomes by one project choice at each timestep, and utility by the number of approved choices. There is no restriction against repeating projects. These hypotheses match the finite-agent problem used by the prover. The theorem citation is accurate and sufficiently precise. [Theorem 3.1 and model definitions](https://arxiv.org/html/2408.13637v2#S3).
The prover appropriately supplies a reduction to the distribution-over-types formulation; it does not assume that the cited theorem already classifies that formulation.
For singleton approvals \(S_{\theta t}=\{a_{\theta t}\}\), the equivalence
\[
u_\theta(o)\geq 1
\quad\Longleftrightarrow\quad
\text{there exists }t\in\{1,\ldots,\ell\}\text{ with }o_t=a_{\theta t}
\]
follows directly from the stated utility definition.
The certificate specifies all \(\ell\) project choices. Its stated length \(O(\ell\log(m+1))\) is polynomial in the input length under the indexed representation used in the write-up. Explicit trajectory listing and nonempty support prevent an exponentially large, implicitly represented horizon.
Checking project validity and at most \(\tau\ell\) comparisons verifies every supported type’s constraint. The stated verification bound \(O(L+\tau\ell\log(m+1))\) is consistent with binary project indices and indexed storage.
Equality is tested on entire trajectories, so the retained trajectories are pairwise distinct and retain singleton approvals at every timestep. Since the source instance has \(n\geq 1\), the resulting support satisfies \(1\leq\tau\leq n\).
Removing duplicate trajectories does not remove a distinct feasibility constraint: agents with identical trajectories have identical utility for every outcome. No dependence on the number of possible trajectories is introduced.
With \(q=\lceil\log_2\tau\rceil\), the inequality \(2^q\geq\tau\) guarantees that the final numerator \(2^q-\tau+1\) is positive. All other masses are positive as well. The displayed sum is correct and equals \(1\).
The boundary case \(\tau=1\) is explicitly covered: \(q=0\), the first mass range is empty, and the sole mass equals \(1\). The numerator and denominator lengths give the stated \(O(\log(\tau+1))\) bits per mass. Thus the construction meets even the claimed restriction to dyadic masses.
Every original agent has a retained representative with exactly the same trajectory and therefore exactly the same utility for every outcome. Conversely, every retained type represents an original agent. Consequently, the two universal utility requirements are equivalent for each outcome, and hence their existential feasibility questions are equivalent.
The assigned masses do not enter these requirements. Their arbitrary positive values therefore create no additional condition that could invalidate the equivalence.
Pairwise deduplication requires at most \(O(n^2)\) trajectory comparisons, each costing \(O(\ell\log(m+1))\). Together with input processing and mass construction, the stated bounds are polynomial in the explicitly listed source input length.
The resulting polynomial many-one reduction establishes NP-hardness. Combined with NP membership, it establishes NP-completeness. The conclusion about polynomial-time solvability being equivalent to \(\mathrm{P}=\mathrm{NP}\) is justified for the explicit input representation in the task.
Finally, there are exactly \(m^\ell\) outcomes, and the stated exhaustive-search bound accounts for checking each one. “Exponential in general” does not assert exponential behavior for every instance, so it causes no issue for cases such as \(m=1\).
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.