d4-conf-sagt-2022-0019 (d4-conf-sagt-2022-0019)

Given \(m\) tasks with positive durations \(p_i\) and a society supported on \(\tau\) preferred schedules, each with positive binary-rational mass \(\mu_t\) summing to \(1\), compute a permutation \(S\) minimizing \(\Phi_\mu(S)=\sum_t \mu_t\sum_i |C_i(S)-d_{i,t}|\), where \(C_i(S)\) is task \(i\)’s completion time in \(S\), and \(d_{i,t}\) is its completion time in type \(t\)’s preferred schedule.

There are \(m\geq 1\) tasks with positive binary-rational durations \(p_i\). Every schedule is a permutation of all tasks, executed on one machine from time \(0\), without idle time or preemption.
A society is given by its support: \(\tau\geq 1\) distinct preferred schedules \(V_t\), each with positive binary-rational mass \(\mu_t\), where \(\sum_{t=1}^{\tau}\mu_t=1\). Here \(\tau\) is the support size, not the number \(m!\) of possible types.
Let \(C_i(S)\) be task \(i\)'s completion time in schedule \(S\), and set \(d_{i,t}=C_i(V_t)\), using the same durations in every schedule.
The problem is to compute a permutation \(S\) minimizing \(\Phi_\mu(S)=\sum_{t=1}^{\tau}\mu_t\sum_{i=1}^{m}|C_i(S)-d_{i,t}|\); any minimizing permutation is acceptable. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).

Is exact minimization of \(\Phi_\mu\) polynomial-time solvable in \(m,\tau,L\), or is it NP-hard?

For a finite electorate with equally weighted voters, minimizing total absolute completion-time deviation is strongly NP-hard. With exactly two equally weighted voters, either preferred schedule is optimal.

Result

Exact minimization is NP-hard when the support size \(\tau\) is part of the input. This follows from the finite-electorate hardness premise in the question by aggregating identical votes. The conclusion also holds if “binary-rational” is interpreted strictly as requiring dyadic masses.

The reduction does not establish hardness for any particular fixed support size.

1. Aggregating identical votes

Use the stated hardness result as a premise. Consider an instance with \(n\) equally weighted voters whose preferred permutations are \(R_1,\ldots,R_n\). Its objective is
\[ F(S)=\sum_{r=1}^{n}\sum_{i=1}^{m}|C_i(S)-C_i(R_r)|. \]

Let \(V_1,\ldots,V_\tau\) be the distinct permutations appearing among these votes, and let \(c_t\) be the multiplicity of \(V_t\). Thus
\[ c_t\geq 1,\qquad \sum_{t=1}^{\tau}c_t=n,\qquad \tau\leq n. \]
Keep the durations unchanged and assign mass
\[ \mu_t=\frac{c_t}{n}. \]
These masses are positive and sum to one. For every permutation \(S\),
\[ \Phi_\mu(S) =\sum_{t=1}^{\tau}\frac{c_t}{n} \sum_{i=1}^{m}|C_i(S)-C_i(V_t)| =\frac{F(S)}{n}. \]
Consequently, the two instances have exactly the same minimizing permutations. In particular, any minimizer returned for the support instance solves the original instance.

This transformation has polynomial size and running time. Identical permutations can be grouped by lexicographic sorting, using
\[ O\!\left(nm\log(n+1)\log(m+1)\right) \]
bit operations for comparisons of task labels. Each mass has an encoding of \(O(\log(n+1))\) bits. The output contains at most \(n\) permutations, so it is polynomial in the original input length.

Therefore, a polynomial-time algorithm in \(m,\tau,L\) would yield a polynomial-time algorithm for the given NP-hard finite-electorate problem.

2. If the masses must be dyadic

The fractions \(c_t/n\) need not be dyadic. The following modification proves hardness under that stricter interpretation too.

Let \(D\) be a common denominator of the source durations; for example, take the product of their encoded denominators. Define
\[ q_i=Dp_i,\qquad Q=\sum_{i=1}^{m}q_i. \]
All \(q_i\) and \(Q\) are positive integers. For each support permutation, put
\[ a_t(S)=D\sum_{i=1}^{m}|C_i(S)-C_i(V_t)|. \]
Every scaled completion time is an integer between \(0\) and \(Q\), hence
\[ a_t(S)\in\mathbb Z_{\geq 0}, \qquad a_t(S)\leq mQ. \]

The original normalized, scaled objective is
\[ H_0(S)=\sum_{t=1}^{\tau}\frac{c_t}{n}a_t(S) =\frac{DF(S)}{n}. \]
Since \(DF(S)\) is an integer, any two distinct values of \(H_0\) differ by at least \(1/n\).

Choose a power of two \(M\) satisfying
\[ M>4n\tau mQ. \]
For \(t<\tau\), define
\[ k_t=\left\lfloor\frac{Mc_t}{n}\right\rfloor, \qquad k_\tau=M-\sum_{t<\tau}k_t, \qquad \widehat\mu_t=\frac{k_t}{M}. \]
Because \(M>n\) and \(c_t\geq 1\), every \(k_t\) with \(t<\tau\) is positive. Moreover,
\[ k_\tau\geq \frac{Mc_\tau}{n}>0. \]
Thus these are positive dyadic masses summing to one.

For \(t<\tau\), the rounding error has absolute value less than \(1/M\). The last coordinate compensates for their sum. Therefore,
\[ \sum_{t=1}^{\tau} \left|\widehat\mu_t-\frac{c_t}{n}\right| \leq \frac{2\tau}{M}. \]
Writing
\[ \widehat H(S)=\sum_{t=1}^{\tau}\widehat\mu_t a_t(S) =D\Phi_{\widehat\mu}(S), \]
we obtain, uniformly over all permutations,
\[ |\widehat H(S)-H_0(S)| \leq \frac{2\tau mQ}{M} <\frac{1}{2n}. \]

Let \(T\) minimize \(\widehat H\), and let \(S^*\) minimize \(H_0\). If \(T\) were not an original minimizer, the integer gap would give
\[ H_0(T)-H_0(S^*)\geq \frac1n. \]
But optimality of \(T\) for \(\widehat H\) gives
\[ \begin{aligned} H_0(T)-H_0(S^*) &=[H_0(T)-\widehat H(T)] +[\widehat H(T)-\widehat H(S^*)] +[\widehat H(S^*)-H_0(S^*)]\\ &<\frac1{2n}+0+\frac1{2n} =\frac1n, \end{aligned} \]
a contradiction. Hence every dyadic-instance minimizer is an original minimizer.

Finally, this is a polynomial-size construction. If the source input length is \(L_0\), then \(D\) and \(Q\) have polynomially many bits. Taking the smallest suitable power of two gives
\[ \log M=O\!\left(\log(n\tau m)+\log Q\right), \]
so all constructed masses have polynomial encoding length. This completes the reduction even under the dyadic interpretation.

3. Exact running-time bounds

For completeness, the problem admits an exact subset dynamic program.

Define the individual completion-time cost
\[ f_i(x)=\sum_{t=1}^{\tau}\mu_t|x-d_{i,t}|. \]
For a subset \(A\) of tasks, let
\[ P(A)=\sum_{i\in A}p_i, \]
and let \(B(A)\) be the minimum total cost of ordering precisely the tasks in \(A\), starting at time zero. Then
\[ B(\varnothing)=0, \qquad B(A)=\min_{i\in A} \left[B(A\setminus\{i\})+f_i(P(A))\right]. \]

To justify the recurrence, if task \(i\) is last, it completes at \(P(A)\). Removing it leaves a schedule of \(A\setminus\{i\}\), with all other completion times unchanged. Conversely, appending \(i\) to an optimal ordering of that smaller subset attains the corresponding candidate value.

All arithmetic can be performed exactly by clearing the duration and mass denominators. The resulting integers have \(O(L)\) bits: products of input denominators have bit lengths bounded by their total encoded length, and summing the objective terms adds only logarithmically many bits.

Using ordinary quadratic-time integer arithmetic, this yields:

• Evaluation of one permutation: \(O(m\tau L^2)\) bit operations.
• Exact optimization: \(O(2^m m\tau L^2)\) bit operations.
• Dynamic-programming storage, including preferred completion times: \(O((2^m+m\tau)L)\) bits.

Recording a minimizing last task at each subset reconstructs a minimizing permutation.

4. The two-voter case

The hardness conclusion concerns unrestricted support size and is consistent with the stated two-voter result.

Indeed, for two schedules \(V_1,V_2\) of equal mass, the triangle inequality gives
\[ \Phi_\mu(S) \geq \frac12\sum_{i=1}^{m}|C_i(V_1)-C_i(V_2)|. \]
Both \(S=V_1\) and \(S=V_2\) attain this bound.

Thus the target problem is NP-hard in general, despite this easy special case.

⟨structured verdict parsed — rendered above⟩

The output correctly resolves the task: exact minimization is NP-hard when the support size is unrestricted. Both reductions preserve the property needed for the requested output: any returned minimizing permutation solves the source instance. No major or minor mathematical issues were found.

• Use of the hardness premise

The finite-electorate hardness result is explicitly supplied by USER_TASK, so the prover may use it as a premise without proving or citing it separately. The source instance is represented by its explicitly listed voter permutations \(R_1,\ldots,R_n\), as required for the stated polynomial-size transformation.

The prover appropriately limits its conclusion to unrestricted support size. It does not claim hardness for a particular fixed support size or claim that the dyadic reduction establishes strong NP-hardness.

• Aggregation of identical votes

The multiplicities satisfy \(c_t\geq 1\), \(\sum_t c_t=n\), and \(\tau\leq n\). Consequently, the constructed masses \(c_t/n\) are positive and sum to one, and the support permutations are distinct.

The identity \(\Phi_\mu(S)=F(S)/n\) holds for every permutation \(S\). Multiplication by the positive constant \(1/n\) preserves all minimizing permutations, including ties. Thus the reduction satisfies the task’s requirement that any minimizing permutation be acceptable.

The sorting bound is valid: there are \(O(n\log(n+1))\) comparisons, each examining at most \(m\) labels of \(O(\log(m+1))\) bits. Each mass has \(O(\log(n+1))\) encoding length. Since the source explicitly contains \(n\) permutations, the transformation is polynomial in its input length.

• Integer scaling and objective separation

Taking the product of the duration denominators produces a valid common denominator \(D\). Hence \(q_i=Dp_i\) and \(Q=\sum_i q_i\) are positive integers.

Every scaled completion time lies between \(0\) and \(Q\), so each scaled absolute deviation is an integer at most \(Q\). Therefore \(a_t(S)\) is a nonnegative integer bounded by \(mQ\), as stated.

The equality \(H_0(S)=DF(S)/n\) is correct. Since \(DF(S)\) is an integer, distinct objective values differ by at least \(1/n\). This separation statement applies to distinct values, without incorrectly excluding ties.

• Dyadic masses

The choice \(M>4n\tau mQ\) implies \(M>n\). Thus every rounded numerator for \(t<\tau\) is positive. The compensating last numerator satisfies \(k_\tau\geq Mc_\tau/n>0\), and the numerators sum exactly to \(M\).

Each of the first \(\tau-1\) coordinate errors has magnitude less than \(1/M\). The last coordinate compensates for their sum, so the stated total error bound \(2\tau/M\) is valid, although conservative.

Combining this with \(a_t(S)\leq mQ\) yields the uniform strict bound
\[ |\widehat H(S)-H_0(S)|<\frac{1}{2n}. \]
The constants and strict inequality are correct.

The comparison between a rounded-objective minimizer \(T\) and an original minimizer \(S^*\) is valid. Rounded optimality makes the middle difference nonpositive, while the two perturbation terms together are strictly less than \(1/n\). This contradicts the original objective separation whenever \(T\) is not an original minimizer.

The argument establishes the required inclusion of minimizer sets; it does not require every original minimizer to remain optimal after rounding. For \(\tau=1\), the empty sum gives \(k_1=M\), so the construction also covers that edge case.

• Encoding size of the dyadic construction

The product defining \(D\) has bit length bounded by the total denominator encoding length. The scaled durations and their sum \(Q\) consequently have polynomial bit length.

Choosing the smallest suitable power of two gives the stated bound on \(\log M\). Thus the dyadic numerators and denominators have polynomial encoding length. The potentially large numerical value of \(M\) does not invalidate the reduction because it is encoded in binary.

• Subset dynamic program and running times

The recurrence correctly uses the fixed preferred completion times from the full input schedules. When \(i\) is last in an ordering of \(A\), its completion time is \(P(A)\), and deleting it leaves every earlier completion time unchanged. Conversely, appending it realizes the corresponding candidate cost. The base case \(B(\varnothing)=0\) is correct.

Clearing duration and mass denominators permits exact integer arithmetic. Products of denominators, completion-time sums, and objective sums have \(O(L)\) bits under the stated explicit input representation.

There are \(2^m\) states and at most \(m\) candidates per state. Evaluating a candidate cost directly uses \(\tau\) terms. The stated optimization bound \(O(2^m m\tau L^2)\), evaluation bound \(O(m\tau L^2)\), and storage bound \(O((2^m+m\tau)L)\) are valid conservative bounds. Recording a minimizing last task supports reconstruction within these bounds.

• Two equally weighted voters

The coordinatewise triangle inequality gives the displayed lower bound. Either preferred schedule attains equality because one deviation term vanishes and the other equals the distance between the two preferred completion-time vectors. This verifies the special case and is consistent with unrestricted-support hardness.

No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩