# Reading roadmap: The Computational Complexity of Knot Genus and Spanning Area

The paper combines a Boolean-satisfiability reduction with a normal-surface certificate. Interval pairings encode components of compressed surface data; a weighted extension computes additional component information. A separate metric construction treats spanning area.

Source SHA-256: `a9aef372daa3ea7807f26a5f4f39a0b9ce91e107b2d7bb76042683ae547f304d`. Indexed 102,690 characters.

Edges point from prerequisite to consumer. Solid proof edges are attributed inferences, not formal certificates; references remain candidates.

## Internal claim index

### Theorem 1 — `thmnph`

Source lines 152–154.

Reduce one-in-three satisfiability to a genus bound in a varying triangulated three-manifold.

- `branch` (proof_dependency; source_audit_annotation): The converse was shown in the proof of Lemma~\ref{branch}. It then follows from Lemma~\ref{branch} that $K$ bounds an embedded surface of genus at most $m+n$ in $M$ if and only if $C$ is satisfiable with each clause containing exactly one true literal.

### Theorem 2 — `thmgnp`

Source lines 160–162.

Use bounded normal coordinates and topology checks to verify a genus certificate.

- `normalcount` (proof_dependency; source_audit_annotation): We apply Corollary~\ref{normalcount} to verify that $\partial F$ is connected in time bounded by a polynomial in $t \log W$.
- `bound` (proof_dependency; source_audit_annotation): Theorem~\ref{bound} implies that the normal coordinates of this surface are at most $t2^{7t+2}$. There are $7t$ normal coordinates, and each represents a triangle or quadrilateral, so that the total number of intersections with the 1-skeleton satisfies $N \le 28{t^2}2^{7t+2}$. In particular, $\log N$ is bounded above by a polynomial in $t$.

### Theorem 3 — `3mkgnpc`

Source lines 166–168.

Combine the hardness and certificate statements.

- `thmnph` (proof_dependency; source_audit_annotation): \begin{theorem} \label{thmnph} {\sc 3-MANIFOLD KNOT GENUS} is {\bf NP}-hard. \end{theorem} It was established in \cite{HLP:99} that {\sc 3-MANIFOLD KNOT GENUS} is in {\bf PSPACE}.  We improve this bound in Section~\ref{sectiongnp} . \begin{theorem} \label{thmgnp} {\sc 3-MANIFOLD KNOT GENUS} is {\bf NP}. \end{theorem} In combination these two results give: \begin{theorem} \label{3mkgnpc} {\sc 3-MANIFOLD KNOT GENUS} is {\bf NP}-complete. \end{theorem}
- `thmgnp` (proof_dependency; source_audit_annotation): \begin{theorem} \label{thmnph} {\sc 3-MANIFOLD KNOT GENUS} is {\bf NP}-hard. \end{theorem} It was established in \cite{HLP:99} that {\sc 3-MANIFOLD KNOT GENUS} is in {\bf PSPACE}.  We improve this bound in Section~\ref{sectiongnp} . \begin{theorem} \label{thmgnp} {\sc 3-MANIFOLD KNOT GENUS} is {\bf NP}. \end{theorem} In combination these two results give: \begin{theorem} \label{3mkgnpc} {\sc 3-MANIFOLD KNOT GENUS} is {\bf NP}-complete. \end{theorem}

### Theorem 4 — `bound`

Source lines 372–388.

Bound the size of normal coordinates needed for certificates.

### Theorem 5 — `mingenusfund`

Source lines 393–396.

Choose a minimal-genus fundamental spanning surface using a cited existence result.

### Lemma 6 — `branch`

Source lines 528–533.

Translate a satisfying assignment into a spanning surface in a branching complex, and conversely.

### Lemma 7 — `lemma:line:805:35973`

Source lines 805–807.

A periodic pairing has $t = c - a$ orbits on $[a, d]$.

*Extractive statement; proof gist not independently reconstructed.*

### Lemma 8 — `merge1`

Source lines 823–832.

Let $R_1$ be a periodic interval with pairing $g_1$ of period $t_1$. Suppose that there exists an orientation preserving pairing $g_2$ with translation distance $t_2$ and an interval $J_1 \subset R_1$ such that $J_1$ has width $t_1$ and $g_2(J_1) \subset R_1$. Then the orbits of $g_1 \cup g_2$ on $R_1$ are the same as those of a single periodic action on $R_1$ of period $ \mathrm{GCD}(t_1, t_2)$.

*Extractive statement; proof gist not independently reconstructed.*

### Lemma 9 — `merge2`

Source lines 858–865.

Let $R_1$ and $R_2$ be overlapping periodic intervals, associated with pairings $g_1, g_2$ having periods $t_1$ and $t_2$. Suppose that width($R_1 \cap R_2) \ge t_1 + t_2$. Then the orbits of $g_1 \cup g_2$ on $R_1 \cup R_2$ are the same as those of a single periodic pairing on $R_1 \cup R_2$ of period $ \mathrm{GCD}(t_1, t_2)$.

*Extractive statement; proof gist not independently reconstructed.*

### Lemma 10 — `merge3`

Source lines 882–892.

Let $g_1, g_2$ be periodic pairings with periods $t_1, t_2$ and let $J_1, J, J_2$ be intervals with $ g_1(J_1) = J $ and $g_2(J) = J_2 $. Suppose that $J$ is contained in the union $ J_1 \cup J_2$. Then the hypothesis of Lemma~\ref{merge2} is satisfied and the orbits of $g_1 \cup g_2 $ are the same as those of a single periodic pairing of period $\mathrm{GCD}(t_1, t_2)$, acting on the union of the periodic intervals of $g_1, g_2$.

*Extractive statement; proof gist not independently reconstructed.*


Candidate references: `merge2` (internal_reference).

### Lemma 11 — `orbit.same`

Source lines 1013–1019.

A contraction decreases the number of orbits by the width of the contracted interval. Altering a collection of pairings by any of the operations of periodic merger, trimming, truncation and transmission preserves the number of orbits.

*Extractive statement; proof gist not independently reconstructed.*

### Theorem 12 — `orbitcount`

Source lines 1160–1164.

Apply contractions, trimming, mergers, transmissions and truncations; estimate their number using interval widths.

- `orbit.same` (proof_dependency; source_audit_annotation): Lemma~\ref{orbit.same} shows that the operations of transmission, trimming, truncation and merger occurring in Steps (3),(5) and (6) do not change the number of orbits of the collection of pairings.
- `merge2` (proof_dependency; source_audit_annotation): Mergers carried out in Step (4) occur when the conditions of  Lemma~\ref{merge2} are satisfied, and  Lemma~\ref{merge2} shows that they preserve the orbit structure of the collection of pairings.
- `5pairs` (proof_dependency; source_audit_annotation): By Claim~\ref{5pairs}, each time we run through five cycles either the number of pairings decreases or the number of $Z$-close intervals decreases. There are at most $k$ $Z$-close intervals initially, so after $5k$ cycles either there is a reduction in the number of pairings or there are no $Z$-close intervals
- `div2` (proof_dependency; source_audit_annotation): of pairings or there are no $Z$-close intervals remaining.  In the second case the complexity $X$ has decreased by a factor of at least two, by Claim~\ref{div2}.

### Claim 1 — `overlap`

Source lines 1227–1230.

The union of two $Z$-close intervals of equal width is a connected interval.

*Extractive statement; proof gist not independently reconstructed.*

### Claim 2 — `transmit`

Source lines 1240–1244.

Suppose that the domain $[a,b] \subset [1,Z]$ of a pairing $g$ is not $Z$-close. Then the image $[x',y']$ of an interval $[x,y]$ under ${g}^{-1}$ is not $Z$-close.

*Extractive statement; proof gist not independently reconstructed.*

### Claim 3 — `5pairs`

Source lines 1255–1259.

Bound how long the number of close intervals and pairings can remain unchanged.

- `overlap` (proof_dependency; source_audit_annotation): If Case (2), the three intervals $[c_1, d_2], [c_1', d_1']$ and $[a_1', b_1']$ are all $Z$-close and of equal width, and therefore satisfy the hypothesis of Claim~\ref{overlap}.
- `merge3` (proof_dependency; source_audit_annotation): Lemma~\ref{merge3} then implies that two pairings can be merged, and the number of pairings decreases during the execution of Step (4) in the next cycle.

### Claim 4 — `div2`

Source lines 1322–1329.

Relate disappearance of close intervals to a decrease of the width-product potential.

### Corollary 13 — `normalcurvecount`

Source lines 1456–1463.

Encode intersections of a normal curve with triangulation edges as intervals.

- `orbitcount` (proof_dependency; source_audit_annotation): This is precisely the number returned by the orbit counting algorithm. The number of pairings is at most $3t$ and the interval size is $W$. Applying Theorem~\ref{orbitcount}, we can determine the number of components of the normal curve $\gamma$ in time polynomial in $t \log W$.

### Corollary 14 — `normalcount`

Source lines 1517–1524.

Encode normal-surface connectivity using arcs in the two-skeleton.

- `orbitcount` (proof_dependency; source_audit_annotation): We now apply Theorem~\ref{orbitcount} to count the number of components of a normal curve or normal surface.  An obvious algorithm to count components proceeds by marking vertices connected by common edges until all vertices in a component are reached. This procedure takes time linear in the number of edges of the curve. This is equal to the sum of the normal coordinates (called $W$ below), but we can achieve an exponential improvement.

### Lemma 15 — `orbitweights.same`

Source lines 1826–1832.

The operation of transfer sets the weights on $[c, d]$ to zero and preserves the orbit weights of a collection of pairings. The number of distinct weights taken by the weight function on $[1,N]$ increases by at most four following a transfer operation.

*Extractive statement; proof gist not independently reconstructed.*

### Theorem 16 — `weightedcount`

Source lines 1953–1961.

Transport constant-interval weights while counting orbits.

- `orbitcount` (proof_dependency; source_audit_annotation): We will check that the running time of the algorithm is larger than that of the previous unweighted version by a factor which is a polynomial in $ md \log D $. The proof that the algorithm terminates is the same as that given for Theorem~\ref{orbitcount}. There is some extra overhead involved in keeping track of weights that modifies the calculation of the running time. We indicate these additional calculations below.

### Corollary 17 — `eulercount`

Source lines 2004–2012.

Recover component data from appropriately chosen orbit weights.

- `normalcount` (proof_dependency; source_audit_annotation): We begin as in Corollary~\ref{normalcount} by assigning an integer in $[1,N]$ to each point of intersection between the normal surface and an edge of the triangulation, where $N$ is the total number of intersections of $F$ with the 1-skeleton, and again associate three pairings to each face of the triangulation, one to each pair of edges in the face.
- `weightedcount` (proof_dependency; source_audit_annotation): The orbit weights are then the normal coordinates of the components of the normal surface $F$. Each point in the output list $L'$ corresponds to a component of the normal surface with normal coordinates given by the corresponding weight in $\ZZ^{7t}$. Theorem~\ref{weightedcount} tells us that the list $L'$ is computed in time polynomial in $ km d \log D \log N$.

### Corollary 18 — `corollary:line:2052:91018`

Source lines 2052–2059.

Let $M$ be a 3-manifold with a triangulation $T$ containing $t$ tetrahedra and let $F$ be a fundamental normal surface in $M$. There is a procedure for counting the number of components of $F$ and the topology of each component which runs in time polynomial in $t$.

*Extractive statement; proof gist not independently reconstructed.*

### Theorem 19 — `nphard`

Source lines 2126–2128.

Use a metrized branching complex and a thickening to encode a satisfiability instance.

## External inputs and references

### [1] Dehn:10 — `external:Dehn:10`

Source lines 2230–2234.

M. Dehn, ``Uber die Topologie des dreidimensional Raumes'', {\em Math. Annalen}, 69 (1910), 137--168.


Candidate references: `intro` (external_reference).

### [2] GJ:79 — `external:GJ:79`

Source lines 2234–2238.

M.R. Garey and D.S. Johnson, ``Computers and intractability. A guide to the theory of {\bf NP}-completeness'', W. H. Freeman and Co., San Francisco, 1979.


Candidate references: `intro` (external_reference); `sectionnph` (external_reference).

### [3] Hak:61 — `external:Hak:61`

Source lines 2238–2243.

W. Haken, ``Theorie der Normalfl\"achen: Ein Isotopiekriterium f\"ur den Kreisknoten'', {\em Acta Math.}, 105 (1961) 245--375.


Candidate references: `intro` (external_reference).

### [4] Hass:98 — `external:Hass:98`

Source lines 2243–2247.

J. Hass, ``Algorithms for recognizing knots and 3-manifolds'', {\em Chaos, Solitons and Fractals}, 9 (1998) 569--581.

### [5] HLP:99 — `external:HLP:99`

Source lines 2247–2251.

J. Hass, J. C. Lagarias and N. Pippenger, ``The computational complexity of Knot and Link problems'', {\em Journal of the ACM}, 46 (1999) 185--211.


Candidate references: `intro` (external_reference); `ns` (external_reference).

### [6] HL:01 — `external:HL:01`

Source lines 2251–2255.

J. Hass and J. C. Lagarias, ``The number of Reidemeister moves needed for unknotting'', {\em J. Amer. Math. Soc.} 14 (2001), no. 2, 399--428

### [7] Hem:92 — `external:Hem:92`

Source lines 2255–2259.

G. Hemion, {\em The Classification of Knots and $3$-Dimensional Spaces}, Oxford University Press, 1992.

### [8] Hempel:76 — `external:Hempel:76`

Source lines 2259–2263.

J. Hempel, {\em 3-Manifolds}, Princeton University Press, Princeton, NJ 1976.

### [9] Jaco:80 — `external:Jaco:80`

Source lines 2263–2267.

W. Jaco, {\em Lectures on three-manifold topology}, CBMS Regional conference series in mathematics, 43 AMS, Providence, RI, 1980.

### [10] JO:84 — `external:JO:84`

Source lines 2267–2271.

W. Jaco and U. Oertel, ``An Algorithm to Decide If a $3$-Manifold Is a Haken Manifold'', {\em Topology}, 23 (1984) 195--209.


Candidate references: `intro` (external_reference).

### [11] JT:95 — `external:JT:95`

Source lines 2271–2275.

W. Jaco and J. L. Tollefson, ``Algorithms for the Complete Decomposition of a Closed $3$-Manifold'', {\em Illinois J. Math.}, 39 (1995) 358--406.


Candidate references: `intro` (external_reference); `ns` (external_reference); `sectiongnp` (external_reference).

### [12] JR:89 — `external:JR:89`

Source lines 2275–2279.

W. Jaco and J. H. Rubinstein, ``PL Equivariant Surgery and Invariant Decompositions of $3$-Manifolds'', {\em Advances in Math.}, 73 (1989) 149--191.


Candidate references: `ns` (external_reference).

### [13] JVW:90 — `external:JVW:90`

Source lines 2279–2283.

F. Jaeger, D. L. Vertigan and D. J. A. Welsh, ``On the Computational Complexity of the Jones and Tutte Polynomials'', {\em Math. Proc. Cambridge Phil. Soc.}, 108 (1990) 35--53.


Candidate references: `intro` (external_reference).

### [14] Knes:29 — `external:Knes:29`

Source lines 2283–2287.

H. Kneser, ``Geschlossene Fl\"achen in dreidimensionalen Mannigfaltigkeiten'', {\em Jahresbericht Math. Verein.}, 28 (1929) 248--260.


Candidate references: `intro` (external_reference); `ns` (external_reference).

### [15] Moise:52 — `external:Moise:52`

Source lines 2287–2291.

E. E. Moise, ``Affine Structures in $3$-Manifolds, V: The Triangulation Theorem and Hauptvermutung'', {\em Ann. Math.}, 56 (1952) 96--114.


Candidate references: `intro` (external_reference).

### [16] Papadimitriou:94 — `external:Papadimitriou:94`

Source lines 2291–2295.

C.H. Papadimitriou, Computational complexity. Addison-Wesley Publishing Company, Reading, MA, 1994.


Candidate references: `intro` (external_reference).

### [17] Rab:58 — `external:Rab:58`

Source lines 2295–2299.

M. O. Rabin, ``Recursive Unsolvability of Group-Theoretic Problems'', {\em Ann. Math.}, 67 (1958) 172--194.

### [18] Rubinstein:94 — `external:Rubinstein:94`

Source lines 2299–2305.

J.H. Rubinstein, ``An algorithm to recognize the $3$-sphere'', {\em Proceedings of the International Congress of Mathematicians}, Vol. 1, 2 (Zurich, 1994), Birkhauser, Basel, 601--611.


Candidate references: `intro` (external_reference).

### [19] Sch:78 — `external:Sch:78`

Source lines 2305–2310.

Schaefer, T.J. ``The complexity of satisfiability problems'', {\em Proc 10th Ann. ACM. Symp. on Theory of Computing}, ACM, NY, (1978) 216-226.


Candidate references: `sectionnph` (external_reference).

### [20] Schrijver:86 — `external:Schrijver:86`

Source lines 2310–2313.

A. Schrijver, {\em Theory of Linear and Integer Programming}, John Wiley and Sons, 1986.


Candidate references: `ns` (external_reference).

### [21] Sch:61 — `external:Sch:61`

Source lines 2313–2317.

H. Schubert, ``Bestimmung der Primfaktorzerlegung von Verkettungen'', {\em Math. Zeitschr.}, 76 (1961) 116--148.


Candidate references: `intro` (external_reference); `ns` (external_reference); `sectiongnp` (external_reference).

### [22] Seb:90 — `external:Seb:90`

Source lines 2317–2323.

A. Seb\"o, ``Hilbert Bases, Caratheodory's Theorem and Combinatorial Optimization'', in: R.~Kannan and W.~R. Pulleyblank (Eds.), {\em Integer Programming and Combinatorial Optimization}, University of Waterloo Press, 1990, pp.~ 431--455.

### [23] Sei:35 — `external:Sei:35`

Source lines 2323–2327.

H. Seifert, ``\"Uber das Geschlecht von Knoten'', {\em Math. Annalen}, 110 (1935) 571--592.


Candidate references: `intro` (external_reference).

### [24] Thompson:94 — `external:Thompson:94`

Source lines 2327–2330.

A. Thompson, Thin position and the recognition problem for $S^3$. Math. Res. Lett. 1 (1994), 613--630.


Candidate references: `intro` (external_reference).

### [25] Wel:93a — `external:Wel:93a`

Source lines 2330–2334.

D. J. A. Welsh, {\em Complexity: Knots, Colourings and Counting}, Cambridge University Press, 1993.

### [26] Wel:93b — `external:Wel:93b`

Source lines 2334–2338.

D. J. A. Welsh, ``The Complexity of Knots'', {\em Ann. Discr. Math.}, 55 (1993) 159--173.

### [27] Wel:93c — `external:Wel:93c`

Source lines 2338–2342.

D. J. A. Welsh, ``Knots and Braids'', {\em Contemp. Math.}, 147 (1993) 109--123.

## Coverage and limits

{"mode": "native_latex_index", "claims": 23, "sections": 8, "external_references": 27, "source_bibliography_entries": 27, "unresolved_bibliography": 0, "unresolved": 1}

- Reference edges are not certified proof dependencies. Edge direction is prerequisite → consumer.
- Numbers reflect simple source counters; labels and line anchors are authoritative.
- Extractive statements and proof openings are marked; they are not reconstructed proof gists.
- Macros, included files and custom counters require an expanded source or annotated fallback.
- The manuscript uses custom proof macros. Only the explicitly curated edges above are classified as proof dependencies; other references retain their original, unclassified role. No review statuses enter this reading map.
