{"id":"2bb73713-241d-4e5e-8cda-2f41a67724c0","arxiv_id":"1908.04073","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Determining the minimum crossing number of a link is NP-hard, via a reduction from the bipartite crossing number problem.","lead":"The paper proves that deciding whether a link can be drawn with at most a given number of crossings is NP-hard. This is the first formal hardness result for a central question in knot theory, and it also gives NP-completeness for some weaker equivalence notions.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Reverse direction applies Lemma 2.6 to a parity-equivalent diagram, but the lemma's hypothesis requires a crossing-minimal drawing of the actual framework link; the needed parity-robust rigidity statement is not proved.","rationale":"The paper's central claim is that link crossing number is NP-hard, via a reduction from bipartite crossing number. The forward direction is plausible: a low-crossing bipartite drawing yields a low-crossing diagram of the constructed link. The reverse direction is where the proof is least secure. After smoothing self-crossings and selecting one component per weighted group, the proof obtains a weighted diagram D' that is only parity-linking-number equivalent to Lw. The budget inequalities force the same number of crossings among weight-w1 components as the intended framework, but they do not force the diagram to be a diagram of the framework. The proof then invokes Lemma 2.6, whose hypothesis is explicitly about a crossing-minimal drawing of the actual framework L(k,ℓ) and whose proof uses the topological fact that certain pairs are linked, not merely parity-odd. To make the argument valid, the authors would need a parity-robust version of Lemma 2.6: any diagram with the same parity-linking matrix and the same crossing count must have the nested layout of Figure 3. This is not stated or proved. This gap is load-bearing because the extraction of the bipartite drawing of G depends entirely on the geometry of the frame (the arcs ℓ1,ℓ2 and the order of guards), which the lemma is supposed to guarantee. The reader's verdict of CONDITIONAL is appropriate: the gap is likely repairable, since the existing proofs of Lemmas 2.5 and 2.6 mostly rely on crossing patterns rather than the full isotopy class, but the repair is nontrivial and should be made explicit. A secondary but related defect is the assertion that the weighted crossing number of D' is at most c'; as written this is false without an averaging argument over the copies of each weighted component, though the needed argument is standard. Our agreement with the reader is therefore 'agree' on the weakest assumption.","tokens_in":9805,"tokens_out":24890,"duration_ms":256554,"concrete_test":"Prove or disprove the parity-robust rigidity statement for the smallest nontrivial framework L(1,4) (two 4-chains L0,L1 and four hinges): is every diagram with the same pairwise parity-linking matrix as L(1,4) and with exactly 32 crossings among the eight rings and four hinges homeomorphic to the standard nested diagram? Concretely, attempt to draw L0 and L1 side by side (non-nested) and connect each pair (L0,j,L1,j) by a hinge that crosses exactly those two rings twice and nothing else; if such a diagram exists, the reduction fails, and if every attempted drawing forces extra crossings, the rigidity step is sound for this case. A proof for general k would then require extending this argument to all chains, using the budget inequalities exactly as in conditions (i)–(iv).","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Section 3, after constructing the weighted diagram D' from a parity-linking-number-equivalent drawing D, the proof asserts: 'Lemma 2.6 then allows us to conclude that the frame is drawn exactly as described (and shown in Figure 3).' But Lemma 2.6 is stated for a crossing-minimal drawing of the framework L(k,ℓ) itself, and its proof uses the fact that consecutive components of each chain are linked and that each hinge is linked to its two rings. The diagram D' is only known to be parity-linking-number equivalent to Lw; it is not a diagram of L(k,ℓ). The budget inequalities (i)–(iv) show that any two weight-w1 components cross either twice or not at all, matching the parity graph, but they do not by themselves imply that the diagram is homeomorphic to the nested framework of Figure 3. The proof needs a stronger lemma: any diagram whose pairwise parity-linking matrix agrees with the framework and whose w1-subdiagram has exactly (56nU+8)w1^2 crossings must have the framework's layout. This is not a corollary of the stated Lemma 2.6; for example, even-parity pairs can be linked (Whitehead link) and would need four crossings, so ruling out extra crossings requires the budget, and then one must still rule out alternative non-nested arrangements of the chains and hinges. The existing proof of Lemma 2.6 relies on the isotopy class of L(k,ℓ) for the assertion that all crossings are unavoidable and for the K2,4 planarity argument; re-deriving those steps only from parity and crossing counts is nontrivial and is not supplied. Until this parity-robust rigidity statement is proved, the reduction's reverse direction is incomplete.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper claims the first NP-hardness result for the link crossing number problem. The proof reduces from the NP-complete one-sided bipartite crossing number problem (Theorem 2.1, due to Muñoz–Unger–Vrťo) for graphs whose U-vertices all have degree 4 and whose V-order is fixed. The reduction builds a weighted link Lw whose components are unknots organized as a 'framework' of chains (rings) and hinges, augmented by U-guards, V-guards, and edge-link unknots encoding the edges of G; weights w1 > w2 > 1 are chosen as large polynomials so that a threshold c′ separates intended from unintended crossings via inequalities (i)–(iv). Lemma 2.4 replaces each weighted component by several parallel copies, yielding an unweighted link L′ whose isotopy class does not depend on the drawing, and the main theorem asserts c(L′) ≤ c′ if and only if bcr(G) ≤ c. The same framework is claimed to give NP-completeness for the crossing-number problems under parity-linking-number and linking-number equivalence, and NP-hardness under link homotopy and concordance (Corollary 1.2). The paper closes with a discussion of linkedness equivalence, fixed-k crossing numbers, and open questions.","tokens_in":105,"tokens_out":40939,"duration_ms":474175,"significance":"The main theorem, if its proof is completed, resolves an open problem that has been noted explicitly in the knot theory literature: no formal hardness was previously known for computing the crossing number of a link, in contrast to the situation for graph crossing numbers. The reduction's gadget architecture — weighted unknots, rigid chain-and-hinge frameworks with a uniqueness lemma, guards, and edge-links — is clever and likely to be reusable in further topology hardness arguments, and the cabling trick of Lemma 2.4 for removing weights is elegant. The paper correctly identifies the parity-linking structure as the source of hardness and obtains a clean hierarchy of corollaries for coarser equivalence relations. The forward direction is carefully argued, the source problem is an established NP-complete problem (so there is no circularity), and the paper is honest about its limitations (linkedness equivalence, the single-component case, and the link-equivalence bottleneck for NP-membership). However, two load-bearing steps in the reverse direction are not justified as written, and until they are repaired the theorem should be regarded as conditional.","major_comments":[{"comment":"The diagram D′ is only parity-linking-number equivalent to the weighted link Lw; it is not a diagram of the framework L(k,ℓ). Lemma 2.6 is stated and proved only for crossing-minimal diagrams of L(k,ℓ) itself, and its proof uses facts specific to that isotopy class: that the chain and hinge components are actually linked so their crossings are unavoidable, the face structure from Lemma 2.5(iii)–(iv), and the K2,4 planarity argument for the relative nesting of chains. None of these layout conclusions is re-derived for a diagram that merely has the same pairwise linking parities as the framework. The budget argument shows that two weight-w1 components cross either twice or not at all and that the parity graph matches the framework adjacency graph, but this does not force the nested, hinged layout of Figure 3: alternative non-nested arrangements of the chains, different nesting orders, and different placements of the hinges are not excluded. The proof needs a new parity-robust rigidity statement — any diagram whose pairwise parity-linking matrix agrees with that of the framework and whose w1-subdiagram has exactly the framework minimum number of crossings must have the layout of Figure 3 — and this is not a corollary of the stated Lemma 2.6. This gap is load-bearing because it is the only mechanism converting a hypothesized drawing of an arbitrary parity-equivalent link back into a bipartite drawing of G; the invocation also inherits the weighted-count problem of the next comment.","section":"Section 3, reverse direction (statement 'Lemma 2.6 then allows us to conclude that the frame is drawn exactly as…"}],"minor_comments":[{"comment":"The stated value c(D) = 24k+2ℓ appears inconsistent with the framework definition: hinges are added only for 1 ≤ i < k, so there are 4(k−1) hinges, and each hinge must cross each of its two rings at least twice, giving 8k+2ℓ+16(k−1) = 24k+2ℓ−16 rather than 24k+2ℓ. Accordingly the value cframe = (56n_U+8)w1² in Section 3 appears to be 16w1² too large, and the parity graph of the framework contains 28n_U−4 odd pairs, so the lower bound in the reverse direction should be (56n_U−8)w1². The reduction is asymptotically unaffected, but the constants should be re-derived; the displayed formula for cframe also contains a bracket typo.","section":"Lemma 2.6 and Section 3 (value of cframe)"},{"comment":"Taking w1 = 12n_U²w2 + 80n_U² gives only a non-strict inequality in the estimate used to justify condition (i), since the right-hand side is bounded above by exactly w1(12n_U²w2+80n_U²) = w1². Choose w1 strictly larger, for example w1 = 12n_U²w2+80n_U²+1.","section":"Section 3, choice of weights"},{"comment":"The step concluding 'a bipartite drawing of G with at most 4c/4 = c crossings' needs a written counting argument. From a total of 4c crossings among edge-links, choosing for each edge one of its two arcs does not automatically divide the crossing count by four; one must show (as is presumably visible in Figure 5) that the four crossings between two edge-links are distributed one per pair of arcs, so that the chosen arcs cross at most once per crossing pair of edges.","section":"Section 3, final paragraph ('Picking, for each edge, the arc with fewer crossings')"},{"comment":"The symbol c is used for the crossing number of a diagram c(D), the crossing number of a link c(L), the number of crossings in the bipartite drawing of G, and the residual edge-link crossing budget in the reverse direction; similarly k denotes both the input threshold and the number of chains in the framework. This makes Section 3 hard to follow; please use distinct symbols for these quantities.","section":"General notation in Section 3"},{"comment":"The phrase 'up to a homeomorphism of the surface' is ambiguous between the plane and the sphere, and the claim that each chain bounds an inner and an outer face suggests the sphere is intended; please state the convention explicitly.","section":"Lemmas 2.5 and 2.6"},{"comment":"Several of the crossing counts involving edge-links (8n_U²w1, 4n_Vw2, 4c) and the layout claims for the framework and guards are justified only by reference to Figures 3 and 5, but the figure content could not be verified from the text supplied to me. The authors should make these counts checkable from the text or ensure that the figures are legible and clearly labeled.","section":"Figures 3 and 5"}],"recommendation":"major_revision","confidential_remarks":"Both major comments concern the reverse direction of the reduction; the high-level strategy is credible and the result is likely true, but the proof as written is incomplete. I recommend major revision rather than rejection because the two gaps are of a type that can plausibly be repaired within the paper's framework: a parity-robust rigidity lemma and a correct weighted/unweighted budget accounting. The off-by-16 constant in cframe (minor comment 1) suggests that the hinge and crossing counts should be recalculated carefully in any revision. If these gaps are closed, the paper would be a strong contribution to computational topology; I see no fit or novelty problem for the journal, and no evidence of circularity or citation problems."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper proves that determining the crossing number of a link is NP-hard, resolving a question that has been open for decades. The reduction is from bipartite crossing number, using weighted links with u-guards, v-guards, and edge-links to encode the graph. The same construction gives NP-completeness for the weaker notions of parity-linking-number and linking-number equivalence. That is genuinely new and significant. The high-level architecture is sound, the forward direction is clean, and the framework gadgets are carefully designed. The paper is clearly written and the authors honestly flag what they do not prove, such as the single-component knot crossing number case.\n\nThe soft spots are real but repairable. First, in the reverse direction, the authors select one representative per weighted component and claim the weighted crossing number of the resulting drawing D' is at most c' because the unweighted count did not increase. That is not justified as stated; the representative with fewest total crossings need not have few crossings with each particular other representative. A standard averaging argument would fix it, but it is missing. Second, and more substantive, after bounding the crossings among the weight-w1 components, they invoke Lemma 2.6 to conclude the framework is drawn as in Figure 3. But Lemma 2.6 is stated for a crossing-minimal drawing of the actual framework link, while D' is only parity-linking-number equivalent to Lw. The budget rules out extra crossings, but it does not by itself force the nested layout. You need a stronger parity-robust rigidity statement: any diagram with the same pairwise linking parities and the same crossing count must have the framework layout. That statement is likely true, but it is not proved here, and re-deriving Lemma 2.6 under those weaker hypotheses requires nontrivial work. Third, there is a minor indexing typo: the hinge range in the framework definition should be 0 ≤ i < k, not 1 ≤ i < k, to match the crossing count and the proof.\n\nNone of this makes me doubt the result. The approach is credible, and the published version probably fixes these gaps. But the arXiv v1 is not fully self-contained. This is the paper to cite for \"link crossing number is hard.\" It deserves a serious referee, not a desk reject, but the referee should insist on the missing rigidity lemma and the averaging argument before acceptance.","headline":"First NP-hardness proof for link crossing number, a genuinely important result, but the arXiv version has two repairable proof gaps in the reverse direction; it deserves peer review with mandatory fixes.","tokens_in":10662,"tokens_out":9298,"would_cite":true,"duration_ms":97832,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["57K10","68Q17","05C10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Testing whether a link diagram represents a link equivalent to one drawn with at most $k$ crossings is NP-hard.","keywords":["link crossing number","NP-hardness","computational topology","knot theory","bipartite crossing number","linking number","weighted links","link diagrams"],"falsifier":"Exhibit, for a small framework $L(2,\\ell)$, a diagram with the same pairwise linking parities and with at most $c(L(2,\\ell)) + t$ crossings for some small $t$, whose layout is not the concentric nested layout of Figure 3. Such an example would refute the parity-robust rigidity claim on which the proof's reverse direction depends.","tokens_in":9532,"feed_emoji":"🔗","tokens_out":8501,"duration_ms":85086,"temperature":0.7,"pith_summary":"This paper establishes that the link crossing number problem is NP-hard: given a link diagram and an integer $k$, deciding whether the represented link is equivalent to one drawn with at most $k$ crossings is computationally intractable unless P = NP. The proof reduces the NP-complete bipartite crossing number problem to link crossing number by encoding a bipartite graph as a weighted link built from chains of unknots, hinges, guards, and edge-links. The same gadget shows NP-completeness for the crossing number problem under linking-number and parity-linking-number equivalence, and NP-hardness under link homotopy and concordance. For the authors, this is the first formal computational hardness result for a fundamental knot-theoretic minimization problem.","feed_headline":"Finding a link's fewest crossings is NP-hard","feed_subtitle":"Even deciding whether a diagram can be redrawn with at most k crossings is intractable unless P=NP.","key_machinery":"The load-bearing gadget is the framework $L(k,\\ell)$: a stack of chains of four unknots, where consecutive chains are bound by four linking unknots called hinges. Lemma 2.6 shows that a crossing-minimal drawing of a framework must be the concentric nested layout of Figure 3, with each chain drawn in the outer face of the next; this rigidity is what lets the reduction translate crossings in a link diagram into the ordering of vertices in a bipartite drawing. The second mechanism is the weighting scheme: each component carries an integer weight, crossings count with the product of weights, and Lemma 2.2 guarantees that connected smoothings, which remove self-crossings, do not change linking numbers modulo 2. Together the weights make the intended crossing count of every gadget unavoidable while keeping the accounting linear in the original graph's crossing number $c$. The final removal of weights via parallel copies relies on the constructed components being unknots drawn without self-crossings.","core_discovery":"The central claim is Theorem 1.1: testing whether a link diagram represents a link equivalent to some diagram with at most $k$ crossings is NP-hard. The authors reduce from bipartite crossing number for graphs whose $U$-vertices have degree 4, whose $V$-vertices have degree 1, and with the $V$-order fixed. Given such a graph $G$, they construct a weighted link $L_w$ whose components are unknots arranged as a framework of four-component chains joined by hinges, plus guard unknots and edge-links that copy the incidences of $G$; a bipartite drawing with $c$ crossings yields a diagram of $L_w$ with $c' = c_f + c_g + 8n_U^2 w_1 + 4n_V w_2 + 4c$ weighted crossings, and weights are then removed by replacing each component with parallel copies. For the reverse direction, they use Lemma 2.2, which says connected smoothing preserves linking parity, to reduce any parity-linking-number-equivalent diagram with at most $c'$ crossings to a weighted drawing with the same parity data, then apply Lemma 2.6 to force the framework into its nested layout and read off a bipartite drawing of $G$ with at most $c$ crossings. This is what makes the link crossing number problem NP-hard.","pith_inferences":["If Lemma 2.6 could be strengthened to hold for any parity-linking-number-equivalent diagram, the same reduction would likely settle the crossing number problem under linkedness-equivalence, which the paper leaves open.","The weighted-framework construction is flexible enough to encode other ordering-constrained optimization problems on bipartite graphs; replacing the edge-links could give hardness for variants such as one-sided crossing minimization with prescribed component groupings.","The paper's concluding question about reducing the number of components suggests a testable route: if the chain-and-hinge framework could be compressed into a single alternating knot, the proof strategy would move toward the still-open knot crossing number problem."],"forward_implications":["Unless P = NP, no polynomial-time algorithm can decide whether a link diagram can be redrawn with at most $k$ crossings.","The hardness persists for natural weaker equivalence relations: link homotopy and concordance; for linking-number and parity-linking-number equivalence the decision problem is NP-complete.","Because the proof only needs the parity of linking numbers, any algorithm based on invariants at least as fine as linking parity still faces NP-hardness.","For any fixed $k$, the problem lies in NP, so the hardness is driven by $k$ being part of the input rather than by any fixed crossing budget."],"supporting_citations":[{"why":"Supplies the NP-complete source problem: bipartite crossing number for graphs with degree-4 $U$-vertices, degree-1 $V$-vertices, and fixed $V$-order.","marker":"[7]"},{"why":"Introduces link homotopy, one of the equivalence notions to which the NP-hardness result is extended in Corollary 1.2.","marker":"[6]"},{"why":"Introduces link concordance, another equivalence notion covered by Corollary 1.2.","marker":"[2]"},{"why":"Provides the framing of link crossing number as an open hardness question and the fixed-$k$ NP upper bound discussed in Remark 1.","marker":"[5]"}],"fun_headline_variants":["Even deciding link crossing number is NP-hard","Link crossing number is NP-hard","Finding fewest link crossings is NP-hard","NP-hard: link crossing number decision","Deciding if a link has ≤k crossings is NP-hard"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The reverse direction applies Lemma 2.6, which is proved only for crossing-minimal diagrams of the actual framework, to a drawing that is merely parity-linking-number equivalent; if such a drawing can avoid the nested layout while staying near the crossing-number budget, the reduction's conclusion does not follow.","fun_headline_variants_meta":{"raw":{"variants":["Even deciding link crossing number is NP-hard","Link crossing number is NP-hard","Finding fewest link crossings is NP-hard","NP-hard: link crossing number decision","Deciding if a link has ≤k crossings is NP-hard"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001289,"raw_usage":{"total_tokens":5201,"prompt_tokens":820,"completion_tokens":4381,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":436,"completion_tokens_details":{"reasoning_tokens":4314}},"tokens_in":436,"tokens_out":4381,"duration_ms":35148,"temperature":1.0,"reasoning_tokens":4314,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:58:05.492706+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit, for a small framework $L(2,\\ell)$, a diagram with the same pairwise linking parities and with at most $c(L(2,\\ell)) + t$ crossings for some small $t$, whose layout is not the concentric nested layout of Figure 3. Such an example would refute the parity-robust rigidity claim on which the proof's reverse direction depends.","supporting_citations":[{"cited_title":"One sided crossing minimization is NP-hard for sparse graphs","cited_arxiv_id":null,"evidence_quote":"Supplies the NP-complete source problem: bipartite crossing number for graphs with degree-4 $U$-vertices, degree-1 $V$-vertices, and fixed $V$-order."},{"cited_title":"Link groups","cited_arxiv_id":null,"evidence_quote":"Introduces link homotopy, one of the equivalence notions to which the NP-hardness result is extended in Corollary 1.2."},{"cited_title":"Fox and John W","cited_arxiv_id":null,"evidence_quote":"Introduces link concordance, another equivalence notion covered by Corollary 1.2."},{"cited_title":"Elementary knot theory","cited_arxiv_id":null,"evidence_quote":"Provides the framing of link crossing number as an open hardness question and the fixed-$k$ NP upper bound discussed in Remark 1."}],"review_version":1}