{"id":"dc3baba2-aaae-4beb-ad0e-b3acda9bd2f2","arxiv_id":"2608.05544","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Computing an Ulam median is NP-hard already for exactly four input permutations, which is the minimum possible since three permutations are easy.","lead":"This paper proves that finding a consensus ranking that minimizes the total Ulam distance to a set of rankings is NP-hard even when only four rankings are given. The result is tight: three rankings are easy, so four is the exact breaking point.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified","rationale":"The paper's reduction is internally consistent and the proof of the central theorem is rigorous. The anchor-block lemma was the only place I expected a hidden flaw, but the argument that an optimal LCS for gamma_i Z cannot use Sigma symbols beyond the first s anchor gaps, and symmetrically for Z delta_i, is correct; the split S_L = symbols in U0...Us and S_R = the rest respects both constraints simultaneously. Lemma 3.5's use of the identity max_tau [LCS(tau,gamma1)+LCS(tau,gamma2)] = |S| + LCS(gamma1,gamma2) is justified by the Ulam triangle inequality and equality at tau=gamma1. The threshold 5s/2 - m is an integer because balanced polarity forces s even, and the gap argument correctly requires both upper bounds to be tight. The only external input is the NP-hardness of (3,B2)-SAT from BKS03; this is a well-established result, and the paper's footnote accurately describes it. I therefore see no reason to adjust the ACCEPT verdict.","tokens_in":11041,"tokens_out":27716,"duration_ms":233065,"concrete_test":"Enumerate all permutations of Sigma union Sigma_b for |Sigma|=1 and |Sigma|=2 (M=2s+1), construct the canonical tau_L Z tau_R of Lemma 3.4 for each pi, and verify each of the four LCS values is >= the corresponding LCS value of pi; any violation would refute the lemma.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After careful review, I find no load-bearing concern. The anchor-block lemma (Lemma 3.4) is the main technical novelty; its two-step proof (sorting anchors, then splitting at threshold s) is valid, and the threshold M=2s+1 correctly forces left-LCSs to use only U0...Us and right-LCSs only U_{s+1}...U_M. Lemma 3.5's optimization over tau_L, tau_R follows from the Ulam triangle inequality and is correctly applied. The converse direction's derivation that both the clause-witness and variable-consistency upper bounds must be tight is sound because LCS lengths are integral. The only external dependency is the NP-hardness of balanced 3-SAT (every literal exactly twice) cited to BKS03; this is a standard, published result and does not constitute a genuine risk. No internally inconsistent step was found.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves that computing an Ulam median is NP-hard even when the input consists of exactly four permutations. The proof is a direct Karp-style reduction from a balanced variant of 3-SAT in which every variable has equally many positive and negative occurrences (in fact, every literal appears exactly twice). The construction encodes each literal occurrence as a distinct symbol and builds four permutations: two clause-witness permutations L1, L2 and two variable-consistency permutations R1, R2, separated by a long anchor block Z of length 2s+1. The main technical tool is Lemma 3.4, which shows that any candidate median can be transformed into a canonical permutation of the form tau_L Z tau_R without decreasing any of the four LCS scores. Lemma 3.5 then computes the optimal total LCS for a fixed partition of the literal-occurrence symbols into S_L and S_R. Combining the gadget lemmas with the threshold 5s/2 - m yields Proposition 3.6: the formula is satisfiable if and only if there is a median whose total Ulam distance to the four inputs is at most 5s/2 - m. Together with the known polynomial-time algorithm for three permutations, this closes the gap between three inputs and an unbounded number of inputs.","tokens_in":11179,"tokens_out":16423,"duration_ms":151756,"significance":"If correct, this is a tight and significant result: it establishes that four is the smallest number of input permutations for which computing an Ulam median is NP-hard, and it sharply separates the Ulam median problem from the edit median on arbitrary strings, where a fixed number of inputs is polynomial-time solvable. The paper's strengths include a general and reusable anchor-block lemma, elementary and complete proofs of all internal lemmas, and a reduction with no free parameters. I checked the anchor-block transformation, the fixed-partition optimum, the equality cases in Lemma 3.3, and the threshold computation in Proposition 3.6; all are consistent. The only external ingredient is the cited NP-hardness of balanced 3-SAT, which is a standard published result and does not undermine the proof. The manuscript is clearly written and the central claim is fully supported.","major_comments":[],"minor_comments":[{"comment":"The phrase 'an Ulam median' should read 'a Ulam median' wherever it appears, and the abstract contains 'Fischeret al.' without the intended space before 'et al.'.","section":"Abstract/Introduction"},{"comment":"Identity (★) is used as a black box; please add the one-line derivation from the Ulam triangle inequality, namely that d_U(tau,gamma1)+d_U(tau,gamma2) is at least d_U(gamma1,gamma2), with equality at tau=gamma1.","section":"Section 3, Lemma 3.5"},{"comment":"The NP-hardness of the balanced 3-SAT variant is the only external ingredient, and the threshold in Proposition 3.6 depends on the equality |Sigma+_x|=|Sigma-_x|; please state explicitly which theorem or result in [BKS03] establishes the exact variant used.","section":"Section 3, reduction setup"},{"comment":"The phrase 'the symbols of Sigma remain in their original locations' is slightly ambiguous; saying 'the positions occupied by the symbols of Sigma are unchanged' would be clearer.","section":"Section 4, Step 1"},{"comment":"The proof of the symmetric identity (3) is compressed; it would benefit from explicitly saying that the first symbol of Sigma in a common subsequence determines the threshold t >= M-s.","section":"Section 4, Step 2b"},{"comment":"The decision version of the problem is not discussed; noting that it lies in NP follows immediately from polynomial-time LCS computation, so the result is NP-completeness for the decision version as well as NP-hardness for the optimization version.","section":"Section 3, Proposition 3.6"}],"recommendation":"accept","confidential_remarks":"This is a clean, self-contained proof with no circularity; the author's coauthorship of [FGHS25] is irrelevant because that paper is cited only as context and is not used in the derivation. The only point I would ask the editor to double-check is that [BKS03] indeed proves the balanced 3-SAT variant stated in the footnote, since the reduction's threshold depends on it; I have no reason to doubt the citation."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The result is exactly what it claims: computing an Ulam median is NP-hard for four input permutations, closing the gap between the polynomial-time three-permutation case and the previous unbounded-permutation hardness. The construction is clean and the proof is careful. The anchor-block lemma (Lemma 3.4) is the real new idea, and it is proved properly. It lets the reduction force any optimal median to place literal symbols entirely on one side of the anchor block, so the clause gadget and variable-consistency gadget act independently. That separation is what makes four permutations suffice, and I have not seen it before.\n\nThe fixed-partition analysis in Lemma 3.5 is sound, including the use of the elementary identity (★) to optimize the internal orders. The converse direction in Proposition 3.6 is tight: because LCS lengths are integral, attaining the threshold forces both upper bounds to be tight, and the construction of the satisfying assignment from the partition works. I checked the inequalities and the threshold computation 5s/2 - m; they line up.\n\nSoft spots are minor. The reduction relies on the NP-hardness of the balanced 3-SAT variant (each literal occurs exactly twice), cited to BKS03. That is a standard published result, so it is not a real risk, but a referee may want the citation verified rather than taken on faith. The paper also claims the reduction is polynomial-time without spelling out the sizes; that is obvious enough. I would not ask for more than a sentence.\n\nOne small note: the author is a co-author of the earlier FGHS25 unbounded hardness paper, but that result is not used in the reduction, so there is no circularity. The self-citation is context.\n\nThis paper is for anyone working on rank aggregation or the complexity of median problems under string metrics. It is short, readable, and the main lemma is reusable. I would take it seriously and send it to a good referee. My own verdict is accept; there is nothing here that needs major revision.","headline":"A clean, correct reduction that settles the Ulam median threshold: NP-hard for four permutations, with a genuinely new anchor-block lemma.","tokens_in":11689,"tokens_out":1575,"would_cite":true,"duration_ms":16551,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68R15"],"pacs":[],"model":"deepseek-v4-flash","headline":"Computing an Ulam median is NP-hard even with exactly four input permutations.","keywords":["Ulam distance","Ulam median","rank aggregation","NP-hardness","longest common subsequence","3-SAT reduction","permutation consensus"],"falsifier":"A polynomial-time algorithm that computes a true Ulam median for every four-permutation instance would refute Theorem 1.1 unless P = NP. More directly, the reduction predicts that for every satisfiable balanced 3-CNF formula the optimal total Ulam distance is exactly $5s/2 - m$ and for every unsatisfiable formula it is strictly larger; exhaustive search over all small formulas could test this predicted separation and would fail without it.","tokens_in":10842,"feed_emoji":"📊","tokens_out":8298,"duration_ms":65381,"temperature":0.7,"pith_summary":"The paper asks how many input rankings are enough to make the Ulam-median consensus problem computationally intractable. It proves that four permutations suffice: given four permutations of the same set of symbols, deciding whether a median with total Ulam distance at most a threshold exists is NP-hard. Because three permutations admit a polynomial-time exact algorithm, this pins the complexity threshold exactly at four. The result matters for rank aggregation, where Ulam distance charges once per displaced item rather than per inverted pair, and it separates the Ulam metric from the ordinary edit metric on strings, where medians of any fixed number of inputs remain easy.","feed_headline":"Four permutations make Ulam median NP-hard","feed_subtitle":"Three rankings are easy; four are not. This closes the exact hard-input threshold.","key_machinery":"The load-bearing objects are the two gadgets and the anchor block. The clause-witness pair $\\beta_1,\\beta_2$ lists each clause's three literal occurrences in one order and in reverse, so a common subsequence can take at most one symbol per clause; its restricted longest-common-subsequence length counts exactly the number of clauses hit by a set $S$. The variable-consistency pair $\\alpha_1,\\alpha_2$ places each variable's positive block before its negative block in one permutation and in the opposite order in the other, so a common subsequence can use at most one polarity per variable; equality at $s/2$ forces each variable's chosen side to contain all positives or all negatives. The anchor block $Z$ of length $2s+1$ separates these two roles: the Anchor-block Lemma shows any candidate median can be rewritten as $\\tau_L Z \\tau_R$ without decreasing any of the four LCS scores, and the fixed-partition optimum identity reduces the problem to optimizing two independent LCS terms. The linking identity is $\\max_\\tau (\\mathrm{LCS}(\\tau,\\gamma_1)+\\mathrm{LCS}(\\tau,\\gamma_2)) = |S|+\\mathrm{LCS}(\\gamma_1,\\gamma_2)$, which follows from the Ulam triangle inequality.","core_discovery":"The central claim is Theorem 1.1: computing an Ulam median is NP-hard even when the input consists of exactly four permutations. The proof is a reduction from the restricted 3-SAT variant in which every clause has three literals and each variable has equally many positive and negative occurrences. For a formula with literal-occurrence set $\\Sigma$, the reduction builds four permutations $L_1 = \\beta_1 Z$, $L_2 = \\beta_2 Z$, $R_1 = Z \\alpha_1$, and $R_2 = Z \\alpha_2$ over an alphabet $\\Sigma \\cup \\{z_1,\\dots,z_{2s+1}\\}$. Here $\\beta_1,\\beta_2$ are clause gadgets whose longest common subsequence is $m$ exactly when a chosen true set hits every clause, $\\alpha_1,\\alpha_2$ are variable-consistency gadgets whose longest common subsequence is $s/2$ exactly when each variable's chosen false set contains all positives or all negatives, and the long anchor block $Z$ forces every optimal median into the canonical form $\\tau_L Z \\tau_R$. The reduction proves that the formula is satisfiable if and only if some permutation has total Ulam distance at most $5s/2 - m$ from all four inputs.","pith_inferences":["A natural testable extension is to determine the best polynomial-time approximation ratio achievable for four-permutation Ulam median, since the reduction's hard threshold leaves room for approximation algorithms.","The anchor-block lemma is stated for arbitrary permutations of the literal occurrence set, so the same construction may transfer to other median problems with an LCS-type formulation, such as weighted or constrained rank aggregation.","The reduction may also yield hardness for Ulam center and for clustering under the Ulam metric with a fixed number of clusters, although the paper does not pursue those consequences.","If the threshold gap is robust under perturbation, the construction could be adapted to prove hardness of approximation for four-permutation Ulam median, but that claim is not established in the paper."],"forward_implications":["Unless P = NP, no polynomial-time algorithm can compute an exact Ulam median for four or more input permutations.","The known polynomial-time algorithm for three permutations and this four-permutation hardness close the problem: the smallest hard instance size is exactly four.","Every polynomial-time approximation algorithm for Ulam median is necessarily non-exact on four inputs unless P = NP.","Any fixed-parameter algorithm parameterized by the number of input permutations would have to become hard already at four inputs.","The result sharpens the algorithmic contrast with edit distance: requiring the median to be a permutation, rather than an arbitrary string, is what makes the four-input case hard."],"supporting_citations":[{"why":"Supplies the base NP-hardness of balanced 3-SAT with equal positive and negative occurrences, the premise on which the reduction is built.","marker":"[BKS03]"},{"why":"Provides the polynomial-time exact algorithm for three permutations that makes the four-permutation hardness tight.","marker":"[CDK21]"},{"why":"Establishes NP-hardness of Ulam median for an unbounded number of permutations, the prior result this paper strengthens to a fixed constant.","marker":"[FGHS25]"}],"fun_headline_variants":["Four permutations seal Ulam median's NP-hardness","Ulam median: hard with exactly four rankings","Three easy, four hard: Ulam median threshold","NP-hardness for Ulam median at four inputs","Closing the gap: Ulam median hard for four"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The reduction inherits the NP-hardness of the balanced 3-SAT variant from earlier work; if that variant were actually tractable, the reduction would no longer imply NP-hardness.","fun_headline_variants_meta":{"raw":{"variants":["Four permutations seal Ulam median's NP-hardness","Ulam median: hard with exactly four rankings","Three easy, four hard: Ulam median threshold","NP-hardness for Ulam median at four inputs","Closing the gap: Ulam median hard for four"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00053,"raw_usage":{"total_tokens":2511,"prompt_tokens":861,"completion_tokens":1650,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":477,"completion_tokens_details":{"reasoning_tokens":1589}},"tokens_in":477,"tokens_out":1650,"duration_ms":10746,"temperature":1.0,"reasoning_tokens":1589,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T11:08:47.061046+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A polynomial-time algorithm that computes a true Ulam median for every four-permutation instance would refute Theorem 1.1 unless P = NP. More directly, the reduction predicts that for every satisfiable balanced 3-CNF formula the optimal total Ulam distance is exactly $5s/2 - m$ and for every unsatisfiable formula it is strictly larger; exhaustive search over all small formulas could test this predicted separation and would fail without it.","supporting_citations":[],"review_version":1}