d4-conf-ijcai-2021-0588 (d4-conf-ijcai-2021-0588)

Given a candidate set \(C\), a finite support \(T\) of complete rankings with rational masses \(\mu_t>0\) summing to \(1\), and a total order \(X\), determine whether \(X\) minimizes \(\sum_{t\in T}\mu_t d_{\mathrm{KT}}(t,Y)\) over all total orders \(Y\) of \(C\).

Given a finite candidate set \(C\), write \(m=|C|\). A society is given by its support: a list \(T\) of \(\tau\) distinct strict total orders of \(C\), each with positive binary rational mass \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Thus \(\tau\) is the support size, not the number of possible rankings. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
The input also contains a strict total order \(X\) of \(C\). Using Kendall tau distance, define \(S(Y)=\sum_{t\in T}\mu_t d_{\mathrm{KT}}(t,Y)\). Recognition asks whether \(S(X)\leq S(Y)\) for every total order \(Y\) of \(C\); tied minimizers all qualify, with no tie-breaking.

Is this recognition problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard under polynomial-time Turing reductions?

For explicitly listed, unweighted voters, Kemeny Consensus Recognition is \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions ([Fitzsimmons and Hemaspaandra](https://www.ijcai.org/proceedings/2021/0028.pdf)).
No result explicitly addressing recognition for the normalized binary rational support representation above was verified.

Result. The problem is \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions. Consequently, it is \(\mathrm{NP}\)-hard under polynomial-time Turing reductions, even with one oracle query. It belongs to \(\mathrm{P}\) if and only if \(\mathrm{P}=\mathrm{NP}\).

1. Definitions and exact verification.

Let \(R\) denote the recognition problem in the question. Kendall tau distance \(d_{\mathrm{KT}}(t,Y)\) counts the unordered candidate pairs on which \(t\) and \(Y\) disagree. Thus \(0\leq d_{\mathrm{KT}}(t,Y)\leq \binom m2\).

An instance fails recognition precisely when some total order \(Y\) satisfies \(S(Y)<S(X)\). Such a \(Y\), encoded as a permutation of the candidates, is a polynomial-length certificate. We must verify the strict inequality using exact arithmetic.

Write each input mass as \(\mu_t=a_t/b_t\), where \(a_t,b_t\) are positive binary integers. Define

\(D=\prod_{t\in T}b_t,\qquad w_t=a_t(D/b_t).\)

Every \(w_t\) is an integer. Normalization gives

\(\sum_{t\in T}w_t=D.\)

For any order \(Z\), its scaled score is the integer

\(Q(Z)=\sum_{t\in T}w_t d_{\mathrm{KT}}(t,Z)=D S(Z).\)

Because \(D>0\), the certificate condition is exactly \(Q(Y)<Q(X)\). Moreover,

\(0\leq Q(Z)\leq D\binom m2.\)

The binary length of \(D\) is at most \(1+\sum_t\log_2 b_t\), hence at most \(L+1\). Therefore the weights and scaled scores have \(O(L+\log(m+1))\) bits. Clearing denominators does not require expanding the society into individual voters.

To verify a certificate, check that \(Y\) is a permutation, construct position tables for the rankings, count pair disagreements, and compare the two integer scores. Put \(B=L+\lceil\log_2(m+2)\rceil\). Using schoolbook integer arithmetic, a conservative bit-operation bound is

\(O\bigl((L+\tau(m+1)^2)B^2\bigr).\)

This includes constructing the common denominator and weights. Consequently, the complement of \(R\) belongs to \(\mathrm{NP}\), so \(R\in\mathrm{coNP}\). The strict inequality ensures that tied minimizers qualify.

2. Transfer from explicitly listed voters.

Theorem 5 of [Fitzsimmons and Hemaspaandra, *Kemeny Consensus Complexity*](https://www.ijcai.org/proceedings/2021/0028.pdf) establishes \(\mathrm{coNP}\)-completeness of Kemeny Consensus Recognition under polynomial-time many-one reductions. Their consensus definition minimizes the sum of Kendall tau distances over explicitly listed, unweighted voters and permits multiple minimizing orders. These are exactly the objective and tie convention needed here.

Take such an instance with voter rankings \(v_1,\ldots,v_n\), where \(n>0\), and proposed order \(X\). Let \(T\) contain the distinct rankings occurring in the voter list. For each \(t\in T\), let

\(k_t=|\{i:v_i=t\}|,\qquad \mu_t=k_t/n.\)

The resulting instance satisfies every support requirement:

• The rankings in \(T\) are distinct strict total orders.
• Each mass is a positive rational with a binary encoding.
• Since \(\sum_t k_t=n\), the masses sum to \(1\).
• The support size satisfies \(\tau\leq n\).

For every total order \(Y\),

\(S(Y)=\sum_{t\in T}\frac{k_t}{n}d_{\mathrm{KT}}(t,Y)=\frac1n\sum_{i=1}^{n}d_{\mathrm{KT}}(v_i,Y).\)

Multiplication by the positive constant \(1/n\) preserves every score comparison, including equality. Hence \(X\) is a consensus of the original election if and only if the constructed support instance belongs to \(R\).

The transformation is polynomial in the explicitly listed input length. More specifically, let \(N\) be that source length. After relabeling candidates by integers, the output length satisfies

\(L=O\bigl((\tau+1)(m+1)\log(m+2)+\tau\log(n+1)\bigr).\)

Each numerator and denominator uses \(O(\log(n+1))\) bits. Directly grouping identical rankings and, if required, reducing the fractions can be performed within a conservative \(O(N^3)\) bit-operation bound. Since the voters are explicitly listed, \(n\leq N\), so both the construction time and output length are polynomial in \(N\).

If the source convention permits an empty electorate, every proposed order is then minimizing; map that case to a fixed valid yes-instance with one ranking of mass \(1\).

Thus this transformation is a polynomial-time many-one reduction to \(R\). The cited hardness theorem implies that \(R\) is \(\mathrm{coNP}\)-hard. Together with Section 1, this proves \(\mathrm{coNP}\)-completeness for the precise normalized binary rational support representation.

3. Why this answers the requested Turing-hardness question.

Let \(A\) be any language in \(\mathrm{NP}\). Its complement \(\overline A\) belongs to \(\mathrm{coNP}\). By the completeness just proved, there is a polynomial-time function \(f\) such that

\(x\in\overline A\ \Longleftrightarrow\ f(x)\in R.\)

A deterministic algorithm with an oracle for \(R\) decides \(A\) by constructing \(f(x)\), making one oracle query, and accepting exactly when the oracle answers no. Therefore \(A\leq_T^p R\).

Since this holds for every \(A\in\mathrm{NP}\), recognition is \(\mathrm{NP}\)-hard under polynomial-time Turing reductions. In particular, a polynomial-time recognition algorithm would imply \(\mathrm{P}=\mathrm{NP}\). Conversely, if \(\mathrm{P}=\mathrm{NP}\), then \(\mathrm{coNP}=\mathrm{P}\), so recognition would be polynomial-time solvable.

⟨structured verdict parsed — rendered above⟩

Verification outcome

The prover resolves the assigned problem correctly. The argument establishes \(\mathrm{coNP}\)-completeness under polynomial-time many-one reductions for the stated normalized binary rational support representation, and then correctly derives \(\mathrm{NP}\)-hardness under polynomial-time Turing reductions with one oracle query.

No major or minor mathematical issues were found.

Step-by-step audit

1. Recognition failure and certificate

The stated equivalence is correct: recognition fails exactly when there exists a strict total order \(Y\) with \(S(Y)<S(X)\). Because the feasible set consists of permutations of the explicitly supplied candidate set, \(Y\) has polynomial encoding length.

The use of strict inequality correctly implements the task’s tie convention. An order with equal score does not witness failure of recognition.

2. Clearing denominators and bounding integer sizes

All arithmetic identities are valid. For positive integer denominators \(b_t\), the product \(D=\prod_t b_t\) is positive and divisible by every \(b_t\). Hence each \(w_t=a_t(D/b_t)\) is a positive integer. Normalization implies \(\sum_t w_t=D\), and consequently \(Q(Z)=DS(Z)\).

Since \(D>0\), comparison of the integer scores preserves both strict inequalities and equalities.

The score bound \(0\leq Q(Z)\leq D\binom m2\) follows from the distance bound and normalization. The binary length estimate for \(D\) is correct: its length is at most \(1+\sum_t\log_2 b_t\), which is bounded by \(L+1\). Also, positivity and \(\sum_t w_t=D\) imply \(w_t\leq D\). Thus the claimed \(O(L+\log(m+1))\) bound for weights and scores is valid.

This argument concerns the bit length of \(D\), rather than its numerical magnitude, and does not require expanding rational masses into voters.

3. Verification time and membership

Checking the certificate permutation, constructing position tables, and counting disagreements over all candidate pairs are sufficient to compute the two scores exactly.

With \(B=L+\lceil\log_2(m+2)\rceil\), the stated bound
\(O((L+\tau(m+1)^2)B^2)\)
is conservative and sufficient. Schoolbook multiplication and division on the relevant integers fit within the \(B^2\) factor; the bound also accommodates the denominator product, weights, distance calculations, and score accumulation.

The cases \(m=0\) and \(m=1\) cause no failure: every distance is zero and no strict improvement exists. Valid inputs necessarily have nonempty support because the positive masses sum to one.

Therefore the certificate establishes membership of the complement in \(\mathrm{NP}\), and recognition belongs to \(\mathrm{coNP}\).

4. Applicability of the cited hardness theorem

The cited result was checked against the original paper. Theorem 5 states that Kemeny Consensus Recognition is \(\mathrm{coNP}\)-complete. The paper specifies polynomial-time many-one reductions, defines voters by strict total orders, and defines a consensus by minimizing the sum of Kendall tau distances. Its definition permits multiple minimizing rankings. Its hardness construction explicitly produces a polynomial-size voter list. Thus the theorem has the representation and tie convention required by the prover’s reduction. [Fitzsimmons and Hemaspaandra, *Kemeny Consensus Complexity*](https://www.ijcai.org/proceedings/2021/0028.pdf)

There is no unverified hypothesis in this application.

5. Transfer to normalized rational support

For a nonempty voter list, grouping identical rankings produces distinct support orders with positive counts \(k_t\). The masses \(k_t/n\) are positive binary rationals and sum to one. The bound \(\tau\leq n\) is correct.

For every feasible order \(Y\), the displayed identity
\(S(Y)=\frac1n\sum_{i=1}^n d_{\mathrm{KT}}(v_i,Y)\)
is exact. Since the factor \(1/n\) is positive and independent of \(Y\), it preserves all score comparisons and therefore preserves recognition in both directions.

The output-length bound accounts for the support rankings, proposed order, and binary numerators and denominators after candidate relabeling. Explicit voter listing makes \(n\) polynomially bounded by source length. The stated \(O(N^3)\) construction bound is conservative enough for grouping rankings and encoding or reducing fractions.

The optional empty-electorate case is handled correctly: every proposed order is minimizing, and the specified replacement is a valid yes-instance.

Thus the reduction establishes \(\mathrm{coNP}\)-hardness for exactly the target representation. Together with membership, it establishes \(\mathrm{coNP}\)-completeness.

6. Turing hardness and the conditional polynomial-time conclusion

For every language \(A\in\mathrm{NP}\), its complement belongs to \(\mathrm{coNP}\). Completeness supplies a polynomial-time many-one reduction from that complement to recognition. Querying the resulting instance and reversing the oracle answer decides \(A\), exactly as written.

This is a valid polynomial-time Turing reduction using one query. It proves the requested \(\mathrm{NP}\)-hardness.

Both directions of the final equivalence are also correct: polynomial-time recognition would imply \(\mathrm{P}=\mathrm{NP}\), and \(\mathrm{P}=\mathrm{NP}\) would place recognition in \(\mathrm{P}\).

Repair feedback

No additional mathematical clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩