Answer: NP-hard, even for dyadic masses; polynomial-time solvability in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
Theorem 1 — class: hardness
Given alternatives \(C\) and a support list of complete rankings \((\sigma^r,\mu_r)_{r=1}^{\tau}\), where each \(\mu_r>0\) is a binary rational and \(\sum_r \mu_r=1\), find a permutation \(\pi\) minimizing \(\sum_{r=1}^{\tau}\mu_r d_{\mathrm{AP}}(\pi,\sigma^r)\), with \(d_{\mathrm{AP}}\) exactly as defined in the paper.
Let \(C\) contain \(m\geq 1\) alternatives. A society is given by its support: \(\tau\) distinct strict complete rankings \(\sigma^r\), each with positive binary-rational mass \(\mu_r\), with \(\sum_{r=1}^{\tau}\mu_r=1\). Here \(\tau\) is the support size, not the number of possible rankings; \(L\) is the total input bit length.
For a permutation \(\pi\), let \(\pi_i\) be its item at position \(i\), and let \(\sigma(x)\) denote the position of item \(x\) in \(\sigma\). Define \(d_{\mathrm{AP}}(\pi,\sigma)=\sum_{1\leq i<j\leq m}\frac{m}{2(j-1)}\mathbf{1}\{\sigma(\pi_i)>\sigma(\pi_j)\}\). This distance is asymmetric: its weights depend on positions in \(\pi\).
Find a permutation \(\pi\) minimizing \(\sum_{r=1}^{\tau}\mu_r d_{\mathrm{AP}}(\pi,\sigma^r)\); any minimizer is allowed. The input distribution is arbitrary, with no generative-model promise.
Is finding such a minimizing permutation solvable in time polynomial in \(m,\tau,L\), or is it NP-hard?
For an explicitly listed finite multiset of rankings, minimizing average AP distance is NP-hard. [Source](https://epasto.org/papers/aaai2016-permutations-full.pdf)
No separate complexity classification for arbitrary binary-rational mass inputs was verified.
Finding a minimizing permutation is NP-hard, even when all masses are dyadic rationals (fractions whose denominators are powers of two). Thus a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
For \(m=1\), the objective is zero. The hardness concerns the problem with unbounded \(m\).
We use the established theorem that, given an explicitly listed nonempty multiset \(P=(\sigma^1,\ldots,\sigma^N)\), finding a permutation minimizing
\(H_P(\pi)=\frac1N\sum_{s=1}^{N}d_{\mathrm{AP}}(\pi,\sigma^s)\)
is NP-hard.
The cited paper defines the distance with weights determined by positions in the first argument, exactly as in this task. Its Theorem 1 and the paragraph immediately following it establish hardness for minimizing average AP distance over arbitrary multisets. Thus both the distance orientation and the absence of a distributional promise match our setting. [De Stefani, Epasto, Upfal, and Vandin, Section 3](https://epasto.org/papers/aaai2016-permutations-full.pdf)
We give a polynomial-time reduction from this problem to the requested support representation. The construction also handles the stricter interpretation of “binary-rational” as dyadic.
For a ranking \(\rho\), let \(\rho^{\mathrm{rev}}\) denote its reversal. For every permutation \(\pi\),
\(d_{\mathrm{AP}}(\pi,\rho)+d_{\mathrm{AP}}(\pi,\rho^{\mathrm{rev}})=\frac{m(m-1)}2.\)
Indeed, for each pair \(i<j\), strictness implies that exactly one of \(\rho\) and \(\rho^{\mathrm{rev}}\) ranks \(\pi_i\) after \(\pi_j\). Consequently, the sum of the two distances is
\(\displaystyle \sum_{j=2}^{m}\sum_{i=1}^{j-1}\frac{m}{2(j-1)} =\sum_{j=2}^{m}\frac m2 =\frac{m(m-1)}2.\)
For \(m=1\), both sums are empty and the identity still holds.
Take a source instance \(P=(\sigma^1,\ldots,\sigma^N)\), where \(N\geq1\).
Let \(T\) be the smallest power of two satisfying \(T\geq2N\). Then \(2N\leq T<4N\), and \(k=(T-2N)/2\) is a nonnegative integer.
Construct a multiset \(Q\) as follows:
The total number of occurrences is \(2N+2k=T\).
Now list the distinct rankings occurring in \(Q\) as \(\eta^1,\ldots,\eta^\tau\). Let \(a_r\) be the multiplicity of \(\eta^r\), and assign mass \(\mu_r=a_r/T\).
These masses are positive, sum to one, and are dyadic because \(T\) is a power of two. The rankings in the resulting support are distinct by construction.
For every candidate permutation \(\pi\), its target objective is
\(\displaystyle F_Q(\pi)=\sum_{r=1}^{\tau}\mu_r d_{\mathrm{AP}}(\pi,\eta^r) =\frac2T\sum_{s=1}^{N}d_{\mathrm{AP}}(\pi,\sigma^s) +\frac{k}{T}\bigl(d_{\mathrm{AP}}(\pi,\rho)+d_{\mathrm{AP}}(\pi,\rho^{\mathrm{rev}})\bigr).\)
Applying the padding identity gives
\(\displaystyle F_Q(\pi)=\frac{2N}{T}H_P(\pi)+\frac{k}{T}\frac{m(m-1)}2.\)
The coefficient \(2N/T\) is positive, and the second term is independent of \(\pi\). Therefore the two objectives have exactly the same minimizing permutations. This also verifies that returning any minimizer is sufficient.
The constructed support satisfies \(\tau\leq N+2\). Since \(T<4N\), each numerator \(a_r\) and the denominator \(T\) require \(O(\log(N+1))\) bits. After relabeling alternatives by integers, the total output length is
\(L=O\bigl((N+2)(m\log(m+1)+\log(N+1))\bigr).\)
Multiplicity counting and construction of the support take polynomial time in the explicitly listed source input size.
Hence an algorithm polynomial in \(m,\tau,L\) for the requested problem would solve the known NP-hard multiset problem in polynomial time. The reduction proves the claimed NP-hardness, including for dyadic masses.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The cited hardness result applies to the stated asymmetric distance, and the reduction preserves every minimizing permutation while producing a valid support with polynomial encoding length. No major or minor mathematical issues were found.
The prover precisely states the source problem: given an explicitly listed nonempty multiset of complete rankings, find a permutation minimizing their average AP distance.
The citation supports this statement. Section 3 defines AP distance using positions in the first argument, with exactly the weights appearing in USER_TASK. Theorem 1 states NP-hardness of AP maximum-likelihood optimization; the immediately following paragraph explicitly states NP-hardness of minimizing average AP distance over arbitrary multisets. Thus neither distance orientation nor a generative-model restriction obstructs its application. [De Stefani et al., Section 3](https://epasto.org/papers/aaai2016-permutations-full.pdf)
The source problem is also explicitly supplied as known in USER_TASK, so reliance on this theorem is justified.
For every pair of positions \(i<j\), the items \(\pi_i\) and \(\pi_j\) are distinct. Because \(\rho\) is strict and complete, reversing it complements their relative order. Exactly one of the two inversion indicators therefore equals one.
The weight remains \(m/(2(j-1))\) in both distances because the first argument remains \(\pi\). Consequently, the displayed sum is correct: each fixed \(j\) contributes \(m/2\), and there are \(m-1\) such positions. The identity
\(d_{\mathrm{AP}}(\pi,\rho)+d_{\mathrm{AP}}(\pi,\rho^{\mathrm{rev}})=m(m-1)/2\)
holds for every \(\pi\).
The empty-sum case \(m=1\) is explicitly and correctly handled.
Since \(N\geq1\), the smallest power of two \(T\geq2N\) satisfies \(2N\leq T<4N\). Both \(T\) and \(2N\) are even, so \(k=(T-2N)/2\) is a nonnegative integer.
The constructed multiset has exactly \(2N+2k=T\) occurrences. The construction remains valid when \(k=0\), when padding rankings already occur in the source, and when \(\rho=\rho^{\mathrm{rev}}\) for \(m=1\): multiplicities simply accumulate.
Listing only rankings that occur produces distinct support elements with positive integer multiplicities \(a_r\). Their multiplicities sum to \(T\), so the masses \(a_r/T\) are positive and sum to one.
Because \(T\) is a power of two, every mass is dyadic. Reducing a fraction, if required by the encoding, preserves that property. Thus the construction satisfies even the stricter interpretation of binary-rational masses.
Grouping equal rankings by multiplicity gives exactly the displayed target objective. Substitution of the verified padding identity yields
\(F_Q(\pi)=(2N/T)H_P(\pi)+(k/T)m(m-1)/2\).
The scaling coefficient is strictly positive, and the additive term is independent of \(\pi\). Therefore the sets of minimizing permutations coincide, including all ties. Returning any target minimizer indeed solves the source optimization problem.
There are at most \(N\) distinct source rankings and two additional padding rankings, giving \(\tau\leq N+2\). Since \(a_r\leq T<4N\), the stated numerator and denominator bit bounds are correct.
After relabeling alternatives, the displayed bound on total output length is valid. Counting multiplicities, reversing a ranking, and constructing the support require polynomial time in the explicitly listed source input size. Accordingly, an algorithm polynomial in \(m,\tau,L\) would yield a polynomial-time algorithm for the known NP-hard source problem.
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.