Three-dimensional topology and computational complexity

The Computational Complexity of Knot Genus and Spanning Area

Ian Agol, Joel Hass and William Thurston

29 pages23 claims indexed27 referencesManuscript 2004-07-10

claude-fable-5-2 medium: aht-repair-np-interface

Completed visible assessment, preserved as a readable check record. It is a model assessment, not a formal certificate. This document contains no private reasoning stream.

Conditional on the counter, the substitution does close the component-counting bottleneck. All three tests need only unweighted orbit counts, with k ≤ 12t and log N polynomial after the candidate's N-versus-W correction. But the stated conditional implication does not yet give a sound NP verifier: the Euler-characteristic formula it relies on is the closed-surface one and overstates χ by half the number of boundary arcs. This is easily repaired by computing V − E + D directly. An explicit orientability check or promise for M should also be added. With those repairs and the listed topological premises, NP membership follows for knots in orientable triangulated 3-manifolds given as input; nothing about hardness in fixed S^3 follows.

R3

Checked statement: Assuming a correct unweighted orbit counter for arbitrary signed interval pairings on [1,N], polynomial in k and log N, substituting it for the original orbit-counting theorem closes the component-counting step of the NP verifier for 3-MANIFOLD KNOT GENUS, subject to the paper's other normal-surface and certificate premises.

Returned assessment: repairable_gap

The component-counting bottleneck is closed by the substitution, but the conditional implication as worded inherits a wrong Euler-characteristic formula from the verifier.

Conditional premise: the counter (candidate parts 1-3) is taken as correct and not audited here.

(a) Three component tests. (i) F connected: orbit count 1 on the Corollary 14 pairings. (ii) Boundary connected: orbit count 1 on the Corollary 13 pairings for the normal curve on the boundary torus. Its arc coordinates on each boundary face are read from the unique adjacent tetrahedron (triangle plus quad coordinates). Line 1676 cites Corollary normalcount here; the curve corollary is the one meant. (iii) Orientability: with F connected and the ambient manifold orientable, 2v(F) is the frontier of a regular neighbourhood, so its count is 2 if F is two-sided (orientable) and 1 otherwise. All three need only the integer number of orbits, each compared with 1 or 2. No weighted output is used anywhere. The Euler characteristic, the essentiality parity and the admissibility checks do not call the orbit counter. Degenerate inputs are harmless: zero-width arc families are dropped, and an empty F or empty boundary gives count 0, not 1, and is rejected.

(b) Reductions. Each normal disk is connected with boundary in the 2-skeleton, so components of F correspond to components of F∩T^(2). These are the orbits of the face-arc pairings on F∩T^(1). Each corner family on a face pairs the r points nearest the vertex on two edges, so it is a single signed interval pairing computable from v(F) and edge offsets in polynomial time. This gives k ≤ 12t for surfaces. For the boundary curve, k ≤ 3·(number of boundary faces) ≤ 12t. The counter accepts arbitrary signed pairings, so no special structure is needed.

(c) Bit sizes. The source sets N equal to 'the weight W' while W is defined as the coordinate sum. The candidate's correction is right: a disk has at most 4 corners, so N ≤ 4W. For a closed normal curve the number of points equals the number of arcs, so N ≤ 2W holds with room. With t the size of the exterior triangulation (at most 576 times the input size), a fundamental witness has N ≤ 7t·4·t·2^(7t+2) = 28t²·2^(7t+2). The doubled surface at most doubles this. So log N and k are polynomial in the input size, and the verifier can reject certificates above the coordinate bound. Polynomial rather than linear time suffices.

(d) Euler characteristic gap. Line 1703 gives χ = (1/2)f_3 − σ + wt, the closed-surface formula (f_3 read as the number of normal triangles). For F with boundary, arcs in boundary faces lie on one disk, not two. Writing T and Q for the numbers of triangles and quads, E = (3T+4Q+b)/2, where b is the number of boundary arcs. The vertex count wt = Σ ε_ij v_j/t_i remains correct. Hence χ(F) = wt − T/2 − Q − b/2, and the printed formula overstates χ by b/2 > 0. Exact example: one normal triangle in a single tetrahedron has T=1, wt=3, b=3; the printed formula gives 2.5, the true value is 1. Since the boundary is nonempty, the printed test understates genus, so 'genus ≤ g' is unsound as written. The candidate says only that the verifier 'checks Euler characteristic' and does not correct this.

(e) Scope. The result covered is NP membership of 3-MANIFOLD KNOT GENUS, with a triangulated orientable 3-manifold M as part of the input and K in its 1-skeleton. Membership restricts to any subclass of instances, including fixed S^3. The Section 3 hardness reduction builds varying manifolds, so nothing here gives NP-hardness for knots in S^3. As the candidate says, that reduction does not use the orbit counter.

Premises used

  • Hypothesis (not audited): the candidate's unweighted counter is correct and polynomial in k and log N for arbitrary signed interval pairings
  • Theorem 'bound': fundamental coordinates < t·2^(7t+2), applied to the exterior triangulation M_K
  • Schubert (Theorem mingenusfund): a minimal-genus spanning surface occurs among fundamental normal surfaces of M_K
  • K bounds an orientable genus-g surface in M iff M_K contains an orientable genus-g surface with one essential boundary curve on the peripheral torus
  • With K null-homologous in M, a connected essential boundary curve of an orientable surface in M_K is a longitude
  • Removing the closed tetrahedra meeting K from the second barycentric subdivision gives a manifold with one torus boundary component
  • The matching, positivity and quadrilateral conditions characterise vectors of embedded normal surfaces, and 2v(F) is the frontier of a regular neighbourhood of F
  • Odd intersection with a closed 1-skeleton cycle on the boundary implies the boundary curve is nonzero in mod-2 homology, and such a cycle exists for the witness
  • Orientability of M (a stated standing assumption)

Missing inputs

  • Topological proofs of the premises above (not supplied; not re-audited)
  • The original orbit-count theorem statement and Section 3 text (not supplied; not needed for this obligation)

Scope changes

  • The conclusion is NP membership for 3-MANIFOLD KNOT GENUS with orientable triangulated M as input; no NP-hardness for fixed S^3 follows.
  • Running-time claims are weakened from 'linear' to polynomial, which suffices.
  • No claim is made about the original printed cycle schedule.

Located concern

AHT-verifier-excerpts lines 1696-1710; candidate-R application claim ('separately checks ... Euler characteristic')

The printed Euler-characteristic formula is the closed-surface formula and is wrong for the bounded surface F in M_K. The candidate inherits it without correction.

One normal triangle in a one-tetrahedron triangulation: printed formula gives 1/2 − 1 + 3 = 5/2, true χ = 1. In general the printed value exceeds χ by b/2, with b the number of boundary arcs, and b > 0 here. The computed genus is then too small, so surfaces of genus above g can be accepted.

Compute χ = V − E + D directly: V is the sum of edge weights, E is the sum over all faces (interior and boundary, each once) of arc counts, D = Σ v_j. Equivalently subtract b/2 from the printed formula. All are polynomial-time arithmetic on O(t)-bit integers. Then genus = (1−χ)/2 and the test is genus ≤ g.

Without the fix the verifier is unsound, so the conditional implication fails as literally stated. With it, the implication holds. The fix is independent of the orbit counter.

Located concern

AHT-verifier-excerpts lines 1625-1633, 1690

The doubling test needs M orientable, but the listed polynomial checks do not include orientability of M.

In a non-orientable M, two-sidedness and orientability of F differ, so a count of 2 for 2v(F) does not certify that F is orientable.

Add a polynomial-time orientability check of the triangulation, or state orientability as a promise on instances, as the introduction does.

Minor: it fixes the exact problem covered (orientable ambient manifolds).

Located concern

AHT-verifier-excerpts lines 1469, 1528, 1676

The source conflates the coordinate sum W with the intersection count N, and cites the surface corollary for the boundary curve.

A quad contributes 1 to the coordinate sum but 4 intersection points.

Already handled by the candidate (N ≤ 4W, and N ≤ 2W for arcs). Use Corollary 13 on the boundary triangulation with induced arc coordinates.

None after the candidate's correction; log N changes by O(1).

Outside the audit

  • Candidate parts (1)-(3): correctness and complexity of the modified schedule
  • Topological foundations: Schubert's theorem, the Hass-Lagarias-Pippenger coordinate bound, normal-surface admissibility conditions, construction of M_K
  • Section 3 NP-hardness construction (text not supplied)
Source record

Additional supporting archive items are identified in the original report. View the manuscript hashes and repository snapshot.

Cite this review

If this review or its supporting reports inform your work, please cite it.

Igor Rivin. Review of The Computational Complexity of Knot Genus and Spanning Area. Math Referee, .

Download .bib
View BibTeX
@misc{rivin2026review-human-agol-hass-thurston-knot-genus,
  author = {Rivin, Igor},
  title = {{Review of The Computational Complexity of Knot Genus and Spanning Area}},
  year = {2026},
  month = {November},
  date = {2026-11-19},
  howpublished = {Math Referee},
  url = {https://mathreferee.dimensionreducers.ai/papers/human-agol-hass-thurston-knot-genus/panel/},
  note = {Review report}
}