Answer: \(\mathrm{NP\text{-}complete}\), and hence \(\mathrm{NP\text{-}hard}\), even for equal masses and uniform-grid profiles
Theorem 10 — class: hardness
Given a (2n) × (2n −1) matrix M, deciding if there is an SR instance I with MAI = M is NP-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), rational masses \(\mu_t\), and piecewise-constant profiles \(R_t:[0,1]\to[0,1]\) on quantile blocks induced by \(\mu\), decide whether strict type orders \(\succ_t\) over \(T\setminus\{t\}\) exist such that, whenever type \(u\) occupies quantile \(z\) in \(t\)'s order, \(R_t(z)\) equals the normalized position of \(t\) in \(u\)'s order; the equal-mass step-function case is the matrix-realizability problem of Theorem 10.
Let \(T\) be a finite set of types with positive rational masses \(\mu_t\) summing to \(1\), and let each \(R_t:[0,1] o[0,1]\) be a rational piecewise-constant function. For a strict order \(\succ_t\) of \(T\setminus\{t\}\), type \(u\) occupies the block \(B_t(u)=[\sum_{v\succ_t u}\mu_v/(1-\mu_t),(\sum_{v\succ_t u}\mu_v+\mu_u)/(1-\mu_t))\). Define \(u\)'s normalized position of \(t\) as \( ho_u(t)=(\sum_{v\succ_u t}\mu_v+\mu_t)/(1-\mu_u)\). The mass-profile realizability problem asks whether orders \((\succ_t)_{t\in T}\) exist such that \(R_t(z)=\rho_u(t)\) for every \(u\ne t\) and \(z\in B_t(u)\).
Is mass-profile realizability solvable in polynomial time, or is it NP-hard?
For equal masses, after rescaling entries by \(|T|-1\), this is the mutual-attraction-matrix realizability problem; it is NP-complete.
No result for the mass-profile formulation above is verified here.
Mass-profile realizability is \(\mathrm{NP\text{-}hard}\), even under the following restrictions:
\[ 0,\frac1{|T|-1},\ldots,\frac{|T|-2}{|T|-1},1; \]
\[ \left\{\frac1{|T|-1},\ldots,1\right\}. \]
Under the standard finite encoding of rational piecewise-constant functions by rational breakpoints and values, the problem is in \(\mathrm{NP}\). Consequently, it is \(\mathrm{NP\text{-}complete}\).
Use the stated nearest known result: mutual-attraction-matrix realizability is \(\mathrm{NP\text{-}complete}\).
An instance is a matrix
\[
A\in\{1,\ldots,n-1\}^{n\times(n-1)}.
\]
For a family of strict orders, let
\[
\operatorname{rank}_u(t)
=
1+\left|\{v\in T\setminus\{u\}:v\succ_u t\}\right|.
\]
If the agents in type \(t\)'s order are
\[
u_{t,1}\succ_t u_{t,2}\succ_t\cdots\succ_t u_{t,n-1},
\]
then their mutual-attraction matrix has entries
\[
A_{t,k}=\operatorname{rank}_{u_{t,k}}(t).
\]
The realizability question asks whether orders with these entries exist.
Let \(A\) be a mutual-attraction-matrix instance with \(n\) rows. Construct a mass-profile instance as follows.
Set
\[
T=\{1,\ldots,n\}
\qquad\text{and}\qquad
\mu_t=\frac1n
\]
for every \(t\in T\).
For \(z\in[0,1)\), let
\[
R_t(z)=\frac{A_{t,k}}{n-1}
\quad\text{whenever}\quad
z\in
\left[\frac{k-1}{n-1},\frac{k}{n-1}\right),
\]
where \(k\in\{1,\ldots,n-1\}\). Define \(R_t(1)\) arbitrarily, for example by
\[
R_t(1)=\frac{A_{t,n-1}}{n-1}.
\]
The value at \(1\) is irrelevant because every block \(B_t(u)\) is right-open and contained in \([0,1)\).
All masses, breakpoints, and values are rational and have polynomial encoding length.
Fix any family of orders and suppose that \(u\) is the \(k\)-th type in \(t\)'s order. Exactly \(k-1\) types precede \(u\), so
\[
\sum_{v\succ_t u}\mu_v=\frac{k-1}{n}.
\]
Moreover,
\[
1-\mu_t=1-\frac1n=\frac{n-1}{n}.
\]
Consequently,
\[
B_t(u)
=
\left[
\frac{(k-1)/n}{(n-1)/n},
\frac{k/n}{(n-1)/n}
\right)
=
\left[
\frac{k-1}{n-1},
\frac{k}{n-1}
\right).
\]
Now let
\[
\ell=\operatorname{rank}_u(t).
\]
There are exactly \(\ell-1\) types above \(t\) in \(u\)'s order. Therefore
\[
\rho_u(t)
=
\frac{(\ell-1)/n+1/n}{(n-1)/n}
=
\frac{\ell}{n-1}.
\]
Thus the blocks record positions in \(t\)'s order, while \(\rho_u(t)\) records the normalized reciprocal rank of \(t\) in \(u\)'s order.
Suppose \(A\) is realizable as a mutual-attraction matrix. Choose realizing orders and let \(u\) be the \(k\)-th type in \(t\)'s order.
By mutual-attraction realizability,
\[
A_{t,k}=\operatorname{rank}_u(t).
\]
For every \(z\in B_t(u)\), the construction and the equal-mass identities give
\[
R_t(z)
=
\frac{A_{t,k}}{n-1}
=
\frac{\operatorname{rank}_u(t)}{n-1}
=
\rho_u(t).
\]
Hence these orders realize the constructed mass profiles.
Conversely, suppose the constructed mass-profile instance is realizable. Let \(u\) be the \(k\)-th type in \(t\)'s realizing order. On the nonempty block \(B_t(u)\),
\[
R_t(z)=\frac{A_{t,k}}{n-1}.
\]
Mass-profile realizability and the equal-mass formula for \(\rho_u(t)\) imply
\[
\frac{A_{t,k}}{n-1}
=
R_t(z)
=
\rho_u(t)
=
\frac{\operatorname{rank}_u(t)}{n-1}.
\]
Multiplying by \(n-1\) yields
\[
A_{t,k}=\operatorname{rank}_u(t).
\]
This holds for every \(t\) and every position \(k\). Therefore the same orders realize \(A\) as a mutual-attraction matrix.
We have proved
\[
A\text{ is realizable}
\quad\Longleftrightarrow\quad
\text{the constructed mass-profile instance is realizable}.
\]
Since the construction has \(n(n-1)\) profile pieces and uses rationals of polynomial bit length, it is a polynomial-time many-one reduction. This proves \(\mathrm{NP\text{-}hardness}\).
Assume each rational piecewise-constant function is represented by a finite list of rational breakpoints and values.
A certificate consists of one permutation of \(T\setminus\{t\}\) for every \(t\). Its total size is polynomial.
Given the certificate, one can:
Rational addition, comparison, and equality are polynomial-time operations in the total bit length. The verification is therefore polynomial-time, proving membership in \(\mathrm{NP}\).
The equal-mass instances are a literal special case of the mass-profile formulation, not merely an analogy. Hence the known \(\mathrm{NP\text{-}complete}\) mutual-attraction-matrix problem transfers directly. Mass-profile realizability is therefore \(\mathrm{NP\text{-}complete}\) under the standard explicit encoding.
⟨structured verdict parsed — rendered above⟩
The reduction correctly identifies equal-mass mass-profile instances with mutual-attraction-matrix instances. Both directions of the reduction are valid, and the construction is polynomial in the source-instance size. The claimed NP-hardness is established.
The NP-membership argument is sound in substance but leaves the endpoint convention for encoded piecewise-constant functions implicit. There is also a minor unaddressed edge case at \(n=1\). These are expositional gaps, not defects in the central reduction.
The prover invokes the supplied premise that mutual-attraction-matrix realizability is NP-complete and formulates its instances as matrices \(A\in\{1,\ldots,n-1\}^{n\times(n-1)}\).
The definition
\[ \operatorname{rank}_u(t) = 1+\left|\{v\in T\setminus\{u\}:v\succ_u t\}\right| \]
correctly gives the one-based position of \(t\) in \(u\)'s order. If \(u_{t,k}\) is the type at position \(k\) in \(t\)'s order, then requiring
\[ A_{t,k}=\operatorname{rank}_{u_{t,k}}(t) \]
is exactly the source realizability condition used by the reduction.
This use of the source result is justified by the nearest-known-result premise supplied in the task. It assumes that the NP-completeness statement applies to precisely this row-and-position matrix convention; the task's statement that the equal-mass formulation becomes that problem supports this identification.
The construction sets \(\mu_t=1/n\) and defines \(R_t\) on the \(k\)-th grid interval by
\[ R_t(z)=\frac{A_{t,k}}{n-1}. \]
For \(n\geq 2\), all masses are positive and sum to \(1\). Since \(A_{t,k}\in\{1,\ldots,n-1\}\), every profile value lies in
\[ \left\{\frac1{n-1},\ldots,1\right\}. \]
The profiles have exactly \(n-1\) intervals per type, so the construction has \(n(n-1)\) pieces. The denominators and numerators have polynomial bit length. Thus the construction is polynomial-time.
The value \(R_t(1)\) is irrelevant because every block is right-open. In particular, the final block ends at \(1\) but does not contain \(1\).
If \(u\) is at position \(k\) in \(t\)'s order, precisely \(k-1\) types precede it. Hence
\[ \sum_{v\succ_t u}\mu_v=\frac{k-1}{n}. \]
Using \(1-\mu_t=(n-1)/n\), the block computation gives
\[ B_t(u) = \left[ \frac{k-1}{n-1}, \frac{k}{n-1} \right). \]
This computation is correct, including the first and last positions.
If \(\ell=\operatorname{rank}_u(t)\), then exactly \(\ell-1\) types precede \(t\) in \(u\)'s order. Therefore
\[ \rho_u(t) = \frac{(\ell-1)/n+1/n}{(n-1)/n} = \frac{\ell}{n-1}. \]
This matches the problem's definition, including its additional \(\mu_t\) term. The range is correct: \(1\leq\ell\leq n-1\), so \(\rho_u(t)\in\{1/(n-1),\ldots,1\}\).
Assuming \(A\) is realizable, take realizing orders. If \(u\) is at position \(k\) in \(t\)'s order, then
\[ A_{t,k}=\operatorname{rank}_u(t). \]
The block identity identifies \(B_t(u)\) with the interval on which \(R_t\) has value \(A_{t,k}/(n-1)\), while the normalized-rank identity gives \(\rho_u(t)=\operatorname{rank}_u(t)/(n-1)\). Thus
\[ R_t(z)=\rho_u(t) \]
for every \(z\in B_t(u)\). This direction is correct.
Assuming the constructed profiles are realizable, let \(u\) occupy position \(k\) in \(t\)'s order. The corresponding block has length \(1/(n-1)>0\) for \(n\geq2\). On that block,
\[ R_t(z)=\frac{A_{t,k}}{n-1}. \]
Realizability and the normalized-rank identity give
\[ \frac{A_{t,k}}{n-1} = \frac{\operatorname{rank}_u(t)}{n-1}. \]
Since \(n-1\neq0\), this implies
\[ A_{t,k}=\operatorname{rank}_u(t). \]
Applying this to every row and position proves that the same orders realize \(A\). This direction is correct.
The equivalence is established for every source instance with \(n\geq2\), and the construction is polynomial. Therefore the claimed polynomial-time many-one reduction and NP-hardness follow.
The proof should explicitly exclude \(n=1\), since the formulas divide by \(n-1\). This does not affect NP-hardness because nontrivial source instances have \(n\geq2\), but the domain restriction should be stated.
A family of \(n\) permutations of \(n-1\) elements has polynomial encoding length. Given the permutations, all block endpoints and normalized positions are rational numbers computable with polynomially many rational operations.
Checking that a finitely represented piecewise-constant function equals a specified rational throughout a rational interval is also polynomial-time: only the finitely many encoded pieces intersecting the block need inspection. Exact rational arithmetic has polynomial bit complexity because the number of operations and the cumulative bit lengths are polynomial in the explicit input size.
The write-up does not precisely state the encoding convention at breakpoints. Since realizability requires equality at every point of each block, values at individual breakpoints matter. A verifier needs to know whether pieces are left-closed/right-open, whether endpoint values are separately encoded, and how \(R_t(1)\) is represented. Under the same half-open convention used in the reduction, the stated scan works. This is a minor specification gap rather than a substantive complexity error.
⟨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.