Answer: Polynomial-time solvable: the feasibility problem belongs to \(\mathrm P\), with running time polynomial in \(\tau\) and \(L\) for fixed \(m=3\).
Theorem 3.2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe Fair-NET problem is NP-hard for forests with ∆= 3. Since forests have fvs = 0, Fair-NET is para-NP-hard parameterized by fvs + ∆.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set \(R\) of positive integer reward types, a rational distribution \(\mu\) over \(R\), and a target \(\kappa\), consider candidate mass \(1\) and a job pool of mass \(3\), with reward-\(a\) jobs of mass \(3\mu_a\). For each multiset \(Q\) of three rewards from \(R\) summing to \(\kappa\), let \(\lambda_Q\ge 0\) be the mass of candidates assigned that triple. Does there exist \(\lambda\) such that \(\sum_Q\lambda_Q=1\) and, for every \(a\in R\), \(\sum_Q m_a(Q)\lambda_Q=3\mu_a\), where \(m_a(Q)\) counts occurrences of \(a\) in \(Q\)?
Let \(R\subseteq\mathbb Z_{>0}\) be nonempty, with \(\tau=|R|\), and let \(\kappa\in\mathbb Z_{>0}\). A society is given by its support: the list of its \(\tau\) reward types with positive masses \(\mu_a\) encoded as binary rationals, where \(\sum_{a\in R}\mu_a=1\); \(\tau\) counts supported types, not all possible types. Rewards and \(\kappa\) are binary encoded; let \(L\) be the total input bit length.
Candidate mass is \(1\), job mass is \(3\), and reward-\(a\) jobs have mass \(3\mu_a\). Each candidate receives exactly \(m=3\) jobs with total reward \(\kappa\), and all job mass must be assigned.
Let \(\mathcal Q\) contain every multiset of three elements of \(R\) summing to \(\kappa\), allowing repeated reward types; let \(m_a(Q)\) be the multiplicity of \(a\) in \(Q\). Feasibility means that real masses \(\lambda_Q\geq0\) exist with \(\sum_{Q\in\mathcal Q}\lambda_Q=1\) and \(\sum_{Q\in\mathcal Q}m_a(Q)\lambda_Q=3\mu_a\) for every \(a\in R\).
Is this feasibility problem in \(\mathrm P\), with running time polynomial in \(\tau\) and \(L\) for fixed \(m=3\), or is it NP-hard?
For indivisible jobs, partitioning positive integer rewards into triples of equal total reward is NP-hard; assigning positive labels bijectively to a forest so that every vertex has the same neighbor-label sum is NP-hard even for disjoint unions of three-leaf stars. [Gupta–Zehavi](https://www.ifaamas.org/Proceedings/aamas2021/pdfs/p555.pdf)
Fractional equal-sum triple assignments have been studied for explicitly listed, labeled job occurrences, with triples restricted to distinct occurrences. [Joosten](https://essay.utwente.nl/61447/1/MSc_S_Joosten.pdf) No result for this precise support-encoded mass problem was identified.
The feasibility problem belongs to \(\mathrm P\). For fixed \(m=3\), all permitted multisets can be explicitly enumerated in polynomial time, and feasibility is then decided by a rational linear program of polynomial encoding length.
The proof uses the stated fractional model, including permission to repeat reward types within a triple.
Write the distinct supported rewards as \(R=\{a_1,\ldots,a_\tau\}\). Enumerate every index triple satisfying \(1\leq i\leq j\leq k\leq\tau\), retaining it exactly when \(a_i+a_j+a_k=\kappa\).
Every multiset of three elements of \(R\) has a unique such index representation. Thus this procedure enumerates precisely \(\mathcal Q\), including multisets with repetitions.
There are \(\binom{\tau+2}{3}=O(\tau^3)\) index triples to inspect. Each reward and \(\kappa\) has at most \(L\) bits, so each sum and comparison takes \(O(L)\) bit operations. Consequently, enumeration takes \(O(\tau^3L)\) bit operations.
Let \(N=|\mathcal Q|\). We have \(N=O(\tau^3)\). If \(N=0\), the instance is infeasible because the required candidate mass is \(1\).
Assume \(N>0\), and list the retained multisets as \(Q_1,\ldots,Q_N\). Define the matrix \(A\in\mathbb Z^{\tau\times N}\) by
\(\displaystyle A_{ij}=m_{a_i}(Q_j).\)
Each entry belongs to \(\{0,1,2,3\}\). Because every multiset contains exactly three rewards, each column satisfies
\(\displaystyle \sum_{i=1}^{\tau}A_{ij}=3.\)
Set \(b_i=3\mu_{a_i}\). Consider the linear feasibility system
\(\displaystyle A\lambda=b,\qquad \lambda\in\mathbb R^N,\qquad \lambda_j\geq0\ \text{for every }j.\)
Equivalence. Any assignment feasible under the problem’s definition satisfies this system, since its equations are exactly the reward-type mass constraints.
Conversely, suppose \(\lambda\) satisfies this system. Summing its equations over all supported types gives
\(\displaystyle 3=\sum_{i=1}^{\tau}3\mu_{a_i}=\sum_{i=1}^{\tau}\sum_{j=1}^{N}A_{ij}\lambda_j=\sum_{j=1}^{N}3\lambda_j.\)
The first equality uses the premise \(\sum_{a\in R}\mu_a=1\); the last uses the column sums of \(A\). Dividing by \(3\) yields \(\sum_{j=1}^{N}\lambda_j=1\). Therefore \(\lambda\) also satisfies the required candidate-mass normalization and is feasible under the original definition.
This proves exact equivalence in both directions.
The standard polynomial-time theorem for rational linear programming states that feasibility over the reals of a finite system of linear inequalities with binary-encoded rational coefficients can be decided exactly in time polynomial in its total encoding length. Polynomial-time solvability in this bit model is recalled in the introduction of [Adler–Beling](https://adler.ieor.berkeley.edu/ilans_pubs/lp_algebraic_stoc_1992.pdf).
Its hypotheses hold here:
The standard-form description has encoding length \(O(\tau N+L)=O(\tau^4+L)\). If an inequality-only formulation is required, replace every equality by two inequalities and include the \(N\) nonnegativity inequalities. Even a dense encoding of this formulation has polynomial length, bounded by \(O((\tau+N)N+L)\).
Hence the linear-programming decision step runs in time polynomial in \(\tau\) and \(L\). Together with the enumeration bound, this proves the claimed running time. Since the support is explicitly listed, \(\tau\leq L\), so the algorithm is also polynomial in total input length alone.
Binary reward encoding causes no difficulty: the algorithm enumerates triples of supported types, without iterating through the numerical range of rewards.
For indivisible jobs, the number of triples of each kind must be integral. The present problem permits arbitrary nonnegative real masses, yielding exactly the linear system proved equivalent above. Thus the cited hardness of indivisible assignments does not establish hardness of this fractional problem.
The target question is completely resolved: the stated problem is polynomial-time solvable. Under polynomial-time many-one reductions, it could be NP-hard only if \(\mathrm P=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover correctly resolves the task: the stated feasibility problem belongs to \(\mathrm P\). The enumeration is exhaustive, the linear program is exactly equivalent to the prescribed fractional model, and its encoding length is polynomial in \(\tau\) and \(L\). No major or minor mathematical issues were found.
The supported rewards are distinct because \(R\) is a set. Assigning indices to them therefore gives every three-element multiset a unique representation with \(1\leq i\leq j\leq k\leq\tau\). Numerical sorting of the rewards is unnecessary; ordering their indices suffices.
Retaining precisely those index triples whose rewards sum to \(\kappa\) enumerates exactly \(\mathcal Q\). Repeated indices correctly cover repeated reward types, as the task requires.
The count \(\binom{\tau+2}{3}\) is correct, including when \(\tau=1\). It is \(O(\tau^3)\).
Each input integer has at most \(L\) bits. Adding three such integers increases the bit length by at most two, so the asserted \(O(L)\) bit cost per sum and comparison is valid. The resulting enumeration bound \(O(\tau^3L)\) is justified.
If \(N=0\), the normalization over the empty family cannot equal \(1\). The immediate infeasibility conclusion is correct.
The definition \(A_{ij}=m_{a_i}(Q_j)\) matches the task’s multiplicity constraints. Every entry lies in \(\{0,1,2,3\}\), and every column sums to \(3\), including columns representing repeated types.
Setting \(b_i=3\mu_{a_i}\) gives exactly the required reward-type mass equations.
The forward implication is immediate: a feasible assignment satisfies \(A\lambda=b\) and nonnegativity.
The reverse implication is also complete. Summing the equations gives
\[
\sum_{i=1}^{\tau}b_i
=
\sum_{j=1}^{N}\left(\sum_{i=1}^{\tau}A_{ij}\right)\lambda_j.
\]
The input normalization makes the left side \(3\), while the column-sum property makes the right side \(3\sum_{j=1}^{N}\lambda_j\). Thus the omitted candidate-mass equation follows.
All sums are finite, so their rearrangement needs no additional hypothesis. Together with the imposed nonnegativity, this establishes every condition in the original definition. No integrality or distinct-occurrence restriction has been introduced.
The prover states the relevant theorem precisely enough: feasibility of a finite system with binary-encoded rational coefficients is decidable exactly in polynomial time in its encoding length.
The cited [Adler–Beling introduction](https://adler.ieor.berkeley.edu/ilans_pubs/lp_algebraic_stoc_1992.pdf) does recall polynomial-time solvability of rational linear programming in the binary bit model. The invoked theorem is standard and applicable here.
Its hypotheses are all verified:
The standard-form encoding bound \(O(\tau N+L)\) is valid. The stated dense inequality-form bound \(O((\tau+N)N+L)\) also correctly accounts for explicitly encoding the nonnegativity rows. Both bounds are polynomial.
The theorem concerns real feasibility with rational input coefficients, precisely the situation here. Arbitrary real values of the feasible masses do not invalidate its application.
Finally, the explicit support list ensures \(\tau\leq L\). Consequently, the claimed algorithm is polynomial in the total input length as well as in \(\tau\) and \(L\).
The proof settles the exact support-encoded problem posed by the task. It does not rely on enumerating every numerical reward value, so binary encoding of potentially large rewards causes no pseudopolynomial dependence.
The distinction from indivisible assignments is valid: imposing integrality changes the feasibility problem. The cited indivisible hardness therefore does not contradict this fractional LP algorithm.
The final qualification is also correct: under polynomial-time many-one reductions, NP-hardness of this problem together with its membership in \(\mathrm P\) would imply \(\mathrm P=\mathrm{NP}\).
None. No missing lemma, unjustified theorem application, or unresolved edge case prevents verification.
⟨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.