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

gpt-6.2-sol high: aht-topology

Reviewer record, not the publication verdict. This preserves the model response, including proposed repairs and unadjudicated objections. The curated report rejects the unsupported Schubert scope objection. A later separate audit accepts the modified unweighted schedule under its stated scope; Sol's different amortization proposal remains unaccepted. Only expressly checked findings enter the decision graph.

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.

The coordinate bound admits an independent elementary proof. The genus-hardness and area-hardness reductions have substantive gaps in the printed converses; the new repairs above provide the needed topological and metric arguments, conditional on the cited source-problem hardness. The local NP verifier can be repaired, including the boundary Euler-characteristic formula, but its witness-existence input for general exteriors and its unweighted orbit-counting premise are not certified here. The NP-completeness inference is logically valid subject to those dependencies. The historical cutoff used is 2002-05-06 under the recorded arXiv first-submission fallback; the examined text is v2 dated 2004-07-10 and the journal received date is unverified. Bibliographic dates above are evidence from the supplied TeX, not inspection of the cited versions. Later knowledge cannot be excluded from model training, but no later result is used as evidence or to discharge an original proof obligation. The independent repairs are explicitly distinguished from the printed arguments.

T1

Checked statement: Theorem 4's bounds on primitive extremal-ray generators and minimal Hilbert-basis elements; Theorem 5's existence of a fundamental normal surface realizing minimum spanning genus, in the setting needed by Theorem 2.

Returned assessment: unresolved

The coordinate bounds check independently. New self-contained derivation: set d=7t. A ray with support of size s has matching matrix of rank s−1 restricted to that support: if the kernel there had dimension at least two, the positive coordinates of the ray generator could be perturbed in both directions, contradicting extremality. Choose s−1 independent restricted rows and use the signed maximal minors as a nonzero kernel vector. Every row has Euclidean norm at most 2, even after cancellation of terms common to the two sides of an equation. The determinant bound obtained by orthogonally projecting each row off the span of its predecessors gives absolute minors at most 2^(s−1). Dividing by the common divisor gives the asserted primitive bound, including the empty-minor case s=1. The slice of the cone by sum of coordinates = 1 is a bounded polytope. To decompose a point of the slice, move in both directions in its current face to endpoints on smaller faces and iterate until vertices are reached; these vertices give the extremal rays. In a conic decomposition, a linear dependence among the generators can be used to vary coefficients until one becomes zero, so at most d generators are needed. If an indecomposable integral vector has a coefficient at least one on a primitive generator, subtract that generator; indecomposability then says the residual is zero. Otherwise the coordinate bound is at most d·2^(d−1) < t·2^(7t+2) for t≥1. If the original vector meets the quadrilateral conditions, all nonnegative summands have support contained in its support and meet them too. None of this proves that a minimum-genus surface has an indecomposable vector. The relevant existence assertion is about a proper normal surface in the constructed exterior, not a normal surface with boundary on a knot edge of a closed triangulation. The supplied source does not establish that Schubert's result covers that assertion for all the exteriors in Theorem 2.

Premises used

  • The matching rows and nonnegative cone as displayed in section 2; boundary faces impose no matching rows.
  • Hass–Lagarias–Pippenger, cited for Theorem 4, is not imported in the independent derivation. Cited exact input: Lemma 6.1, the two normal-coordinate bounds. available_from: 1999 at year precision according to the bibliography; date_evidence: AHT-TeX HLP:99; date_basis: stated journal publication year; version: J. ACM 46 (1999), 185–211, actual text uninspected.
  • Schubert is a conditional external premise, not a verified import. Exact input needed: if an input knot has a spanning surface, its compact orientable triangulated exterior with the specified peripheral torus has a connected orientable fundamental proper normal surface of minimum spanning genus, with a single essential boundary component. available_from: unresolved for that precise result; date_evidence: AHT-TeX Sch:61 records a 1961 article, but supplies no theorem location or text from it; date_basis: stated journal publication year for the cited article only; version: Math. Z. 76 (1961), 116–148, uninspected.

Missing inputs

  • Schubert's dated theorem and proof, with a precise reference and hypotheses on the ambient manifold, irreducibility, boundary, and triangulation; or an independent proof of the required general statement.
  • If the cited theorem requires irreducibility or a special boundary triangulation, a reduction or extension covering the exteriors used here, including reducible ones.

Scope changes

  • Separate the abstract cone bounds from normal-surface existence.
  • Interpret spanning normal surfaces in the compact exterior and require a minimum only over a nonempty class.

Located concern

AHT-TeX, mingenusfund, read with the definitions in sections 1 and 2 and its application in section 5

The stand-alone statement omits existence and exterior hypotheses, and the application does not verify the scope of the external result.

On the literal unconditional reading, S¹×{point} in S¹×S² has nonzero integral homology class and no orientable spanning surface. Even when a span exists, a normal surface in a closed triangulation has no boundary: its matching arcs are paired across all faces, and a normal disk does not have an edge of K as boundary. Section 5 resolves the latter mismatch by passing to the exterior. It does not show that the external existence theorem applies to that exterior. For example, a small unknot in a ball in S¹×S² is in the input class, and an essential sphere disjoint from the ball is still essential in its exterior.

State existence only for a knot that spans, specify the exterior and the proper normal representative with one longitudinal boundary, and verify the precise external hypotheses or prove the extension. For Theorem 2, a polynomial-bit normal witness suffices; it need not be fundamental if another size proof is given.

The literal unconditional version has counterexamples. The intended existence statement for the exterior is neither refuted nor established in this audit. The size bounds are independently supported but cannot fill the existence gap.

T2

Checked statement: Theorem 1 and Lemma 6: the branching-surface construction reduces ONE-IN-THREE SAT to the genus threshold n+m, including the comparison of mapped and embedded spans and the polynomial size of the closed orientable output.

Returned assessment: repairable_gap

A satisfying choice gives F₀ and one page per variable. Gluing at the variable circles connects the pages and gives genus n; each clause circle then joins two remaining boundary circles of this connected oriented surface and adds one handle. For the converse, the needed inequality can be proved without homotoping the map to a union of homeomorphisms. New self-contained repair: cut the target along a circle just inside each page at each glued boundary, leaving K uncut. The resulting regions are trimmed copies of the pages and, at each seam, a circle times a finite star of intervals. Make the map PL relative to K and choose the cut levels away from images of source vertices in the product collars, subdividing into linear pieces there. The inverse images of the cuts are finitely many disjoint circles. If one bounds an innermost disk, its boundary loop in the target cut circle has winding zero: that cut circle injects on π₁ into the region receiving the disk. This injection follows from projection for a seam region and from the nontrivial, infinite-order boundary word in the free group of a nondisk orientable page (cut the page to a polygon). The case n+m=0 is immediate separately. Enlarge the innermost disk slightly into the adjacent source collar. Its new boundary maps to the open collar on the other side of the cut and has winding zero there, so replace its map by a filling in that open collar. This removes a cut without changing the source surface or its boundary map. Repeat; all resulting source regions have χ≤0, with the disk exception already handled. Work over F₂. The image of the relative fundamental chain has a constant coefficient on the interior of each page, since internal edges have zero boundary. The coefficient on F₀ is 1 at K, and the sum of incident coefficients at each seam is 0. Thus exactly one literal page per variable has coefficient 1, and each clause has one or three such occurrences, counted with their multiplicity. In each coefficient-one page P, at least one connected source region X maps to (P,∂P) with relative degree one mod 2. Then H¹(P;F₂) injects into H¹(X;F₂): the absolute/relative cup pairing on a compact surface is nondegenerate, as seen by pairing edges of a triangulation with transverse dual edges, with dual chains terminating at the boundary taken relative to it. If a nonzero absolute class pulls back to zero, pair it with a relative class giving evaluation 1. Naturality and degree one give evaluation 1 on X as well, a contradiction. Both regions have boundary, so χ(X)=1−dim H¹(X)≤χ(P). Summing, and using χ≤0 for the other source regions, gives χ(S)≤χ(F₀)+Σχ(selected pages)=1−2n−m−r, where r is the number of selected literal occurrences. If q clauses have three, then r=m+2q. The upper genus bound implies χ(S)≥1−2(n+m), hence q=0. This argument replaces the printed converse; it does not certify its transversality step. For the 3D reduction, use the bands of Figure 2 as disjoint attachment ports. Each seam has a local cross-section made by attaching strips to disjoint subintervals of one strip's side; it is a 2-manifold cross-section with boundary. Orientation-reversing page-boundary maps and height-preserving port maps give an orientable N. Projection to B is continuous. The double has a continuous folding map to N, so an embedded span in the double gives a map of the same source surface to B fixing K, irrespective of tangencies to the doubling locus. Conversely, for a satisfying choice put a horizontal section in each selected literal product at its midheight; on F₀ take a graph whose boundary heights equal the corresponding selected port midpoints and whose height on K is the prescribed one. A piecewise-linear extension of these heights yields an embedded span in N and in the double. This avoids assuming that the product projection admits a section of the entire branching surface.

Premises used

  • The pieces have the genera and boundary counts given in section 3, with one port for every occurrence, including repeated occurrences if allowed.
  • Conditional external hardness input: deciding whether there is an assignment with exactly one true literal in every three-literal clause is NP-hard (the manuscript cites NP-completeness). available_from: 1978 at year precision as cited, with the exact restriction unverified; date_evidence: AHT-TeX Sch:78; date_basis: stated proceedings publication year; version: Proc. 10th ACM STOC (1978), 216–226, uninspected.

Missing inputs

  • The cited version of Schaefer's result, to verify the exact source problem or a hard subfamily admitted by this construction.

Scope changes

  • The input to the genus problem is a varying closed orientable triangulated manifold, not a fixed manifold.
  • The converse concerns maps with domain a spanning surface and the forward direction constructs an embedded orientable span.
  • The NP-hardness conclusion is conditional on the cited source problem's hardness; the topological and encoding repairs do not require the normal-surface results.

Located concern

AHT-TeX, Lemma branch, paragraphs starting 'The map f₁' and 'The image of S₁'; AHT-p7, end of page

Transversality to cutting circles does not make the complementary maps homeomorphisms. The printed proof then needs, but does not prove, a degree-versus-Euler-characteristic inequality.

For a page with boundary, local folds in the interior change the unsigned number of generic preimages while preserving algebraic degree and without adding any preimages of the cutting circles. Thus generic unsigned count is not algebraic degree, although they agree mod 2. Even the claimed strict χ improvement fails: take S₁ to be the span associated to a satisfying assignment for a single three-variable clause. The selected pages are already exactly those of S₁ and the sum of their Euler characteristics equals χ(S₁).

Use the new collar-cut and relative mod 2 degree argument above. Only non-strict χ comparison is needed.

The printed converse is incomplete. The replacement supplies the needed inequality without assuming a particular normal form for the map.

Located concern

AHT-TeX, Lemma branch, construction of S₄

Arbitrary pairings among four boundary circles at a clause are not automatically orientable and compatible with the given maps simultaneously.

After attaching the selected pages at the variable circles, the orientations on their union are fixed up to an overall reversal. At a clause with three selected occurrences, the F₀ circle has one orientation as mapped to the seam, and all three literal circles have the opposite one. Any pairing of the four matches two literal circles somewhere. Identifying that pair so their maps agree to the seam does not reverse their induced boundary orientations.

Do not construct S₄. Use the Euler characteristic sum for the abstract collection of pages and count selected occurrences directly, as above.

The printed genus inference via this particular quotient is not justified; no such quotient is needed to prove the reduction.

Located concern

AHT-TeX, proof of thmnph, triangulation paragraph and doubling; AHT-p6, Figure 2

The stated one-vertex-per-boundary triangulation count is not correct as written, and cell incidence data must be encoded.

A genuine simplicial boundary circle cannot have just one vertex. Even using triangular cells with identifications, with V=c, c boundary edges, and no interior vertices, 3T=2E−c and χ=V−E+T give T=4g+3c−4, not 4g+5c−4. For a disk the stipulated one-vertex construction is unavailable.

Use fixed finite triangulated templates for disks, annuli, pairs of pants and a one-holed torus, with matching boundary subdivisions, assembling the pages with O(n+m) triangles total. Take a constant number of prism layers and triangulate compatibly after attachment and doubling; a constant number of subdivisions suffices to remove cell-identification ambiguities. Put the specified K on a product boundary level included in the cell structure. Output incidence lists with O(log(n+m+2))-bit indices and the binary threshold n+m.

The printed triangle formula is not a valid justification, but the repaired construction still gives O(n+m) tetrahedra and polynomial bit length and construction time.

T3

Checked statement: Theorem 2: witness existence and size, input validation and exterior construction, verification of slope, connectedness, orientability and Euler characteristic, and polynomial bit complexity.

Returned assessment: unresolved

Conditional on the spanning-witness premise in T1 and on polynomial-time interval orbit counting, the verifier works with the repairs below. Write t for the exterior tetrahedron count. A fundamental vector has O(t)-bit coordinates by Theorem 4, so its 7t entries use O(t²) bits; the edge-point count is at most four times the sum of disk counts. Thus the interval endpoints have O(t) bits on the intended witnesses. Matching, nonnegativity and quadrilateral tests suffice for normal realizability: place the parallel compatible disk stacks in each tetrahedron and match the arcs of each type in order. For connectedness, index edge intersections consecutively along each edge. The at most three arc families in each face give that many interval pairings; each disk is attached along its entire polygonal boundary, so components are exactly the orbits of this graph. There are at most 12t pairings. For the boundary use only the normal arcs in the boundary triangles and their edge points, i.e. use the normal-curve corollary. For a connected F, twice its coordinates describe the two local parallel sheets of F, joined globally as the horizontal boundary of a thin interval neighborhood. Transport along F exchanges the sheets precisely when the normal line orientation reverses; in an oriented ambient 3-manifold that is exactly when the orientation of F reverses. Hence the doubled vector has two components precisely when F is orientable. For a single embedded boundary component on the torus, nonzero mod 2 intersection with a supplied edge cycle is a valid test of essentiality. Every essential simple torus curve has primitive slope and hence a nonzero mod 2 class, paired nontrivially by some mod 2 cycle. The 1-skeleton surjects on first homology, and its graph cycles generate its cycle space, so one can use a single edge circuit as a witness. Counting intersection points on its edges gives the parity directly. For the slope implication, the prior integral null-homology test is essential. In the exterior E, the meridian μ has infinite order: the map H₂(M)→H₂(M,E)≅H₂(N(K),∂N(K))≅Z measures intersection with K, and is zero when [K]=0. The relative generator is a meridian disk, so the boundary map injects its meridian into H₁(E). Also the pair of classes (0,[K] in the solid torus) maps to zero in H₁(M); the gluing exact sequence gives a slope λ with longitudinal coefficient 1 that dies in H₁(E). These exact-sequence computations follow from decomposing chains into the two pieces with common torus; the coefficient of a relative meridian disk class is its signed core intersection. A single boundary of an oriented F vanishes in H₁(E), so if it is essential and primitive it is ±λ. A slope with longitudinal coefficient ±1 cobounds an annulus with the core: for slope (p,1) in meridian/longitude coordinates use (e^{is},r e^{ips}) in S¹×D², after a boundary isotopy, and reverse orientation for the other sign. Thus such an F produces the required genus in M; conversely an embedded span restricts to such an F after placing a collar of its boundary in the knot neighborhood. These slope and double-sheet arguments require neither irreducibility nor a recognition theorem for the ambient homeomorphism type.

Premises used

  • Conditional geometric existence: the intended exterior version of Theorem 5 (external attribution and date record in T1). Theorem 4 supplies bit bounds by the independent argument in T1.
  • Conditional computational input: Theorem orbitcount in the supplied manuscript, in its unweighted form, polynomial in the number of pairings and the binary endpoint length. The normal-arc translation is checked here; the general interval algorithm and its complexity proof are not adjudicated in this packet. This is an internal dependency, not an imported historical theorem.
  • The supplied definition of an orientable ambient manifold and orientable spanning surfaces. The Euler-characteristic repair below does not import JT:95.

Missing inputs

  • A proof or a verified cutoff-admissible source of the polynomial-bit minimum-genus witness on the full class of exteriors (T1).
  • An independent conclusion on the unweighted orbit algorithm if the entire polynomial-time verifier is to be certified unconditionally.

Scope changes

  • Use the bounded-genus decision language with a binary nonnegative threshold, not an exact-genus witness assertion.
  • Require a closed orientable ambient input, or restrict to the connected ambient component containing K if disconnected inputs are allowed.
  • Only the full verifier's dependence on an unweighted normal-component procedure is used; weighted orbit counting is not needed.

Located concern

AHT-TeX, section 5, paragraph beginning 'The Euler Characteristic'

The printed Euler-characteristic formula is not an exterior formula: its notation is incomplete and it omits the boundary-edge correction.

For a normal triangle in a single tetrahedron with boundary, the induced disk has V=3, E=3 and one face, so χ=1. The expression V−Σvⱼ+f₃/2, with f₃ interpreted as the triangle count and wt(F)=V, instead gives 5/2. The same boundary correction is necessary for a span in a knot exterior.

New direct calculation: let T and Q be the triangle and quadrilateral disk counts, B the total number of normal arcs on boundary faces, and V the sum over ambient edges of the number of intersection points computed in one local edge occurrence for each edge. Every internal surface arc counts twice among disk sides and every boundary arc once; thus E=(3T+4Q+B)/2 and χ=V−E+T+Q. Use genus (1−χ)/2 after verifying connectedness, orientability and one boundary component. For a face-pairing presentation use local edge occurrences rather than the number of distinct incident tetrahedra.

The stated calculation is not a correct verifier for genus as printed. The replacement is polynomial in the bit size and works for the required boundary case.

Located concern

AHT-TeX, section 5, first two proof paragraphs

Input validation, the exact deletion operation, and the use of 'genus g' instead of the decision bound need to be made precise.

An edge-link test must check a circle for a closed input, and vertex-link Euler characteristic identifies a sphere only after the link is a connected closed surface. Orientability is part of the problem class. Literally subtracting closed tetrahedra can delete the intended interface torus. Moreover, 'if a genus g surface exists, there is a fundamental one of genus g' cannot be an assertion for every g: on a fixed triangulated exterior the coordinate bound allows only finitely many fundamental surfaces, whereas an embedded span can have arbitrarily many local handles added.

Use a genuine simplicial presentation or subdivide the face-pairing presentation and check incidences, link surfaces, and orientation signs on adjacent tetrahedra; verify that K is a single embedded edge cycle. Take the closed complementary subcomplex of the second derived neighborhood. Directly, after one subdivision K is full, and in the next subdivision its closed star is the union of dual vertex blocks for vertices of the subdivided K. Each is a ball (the cone on the subdivided vertex link), adjacent balls share dual edge disks (cones on the edge links), and there are no triple meetings since K is full and one-dimensional. In each ball the two core half-edges run from the center to the centers of its two attachment disks. These balls and disks give a disk neighborhood along the knot; orientability makes it a solid torus. The interface is collared: in each first-subdivision simplex it is the equality of the largest barycentric coordinate on K-vertices and the largest on the other vertices, and varying the total mass on the K-vertices while preserving the proportions on both sets gives a collar. Keep the interface when forming E. Ask for a minimum-genus witness if the answer to the ≤g question is yes, not a fundamental witness of every attainable genus.

The local exterior construction and slope comparison can be made precise with a constant subdivision factor. The change to the minimum quantifier avoids a false universal assertion but does not discharge T1.

Located concern

AHT-TeX, introduction's instance-size convention; section 5, homology and complexity paragraphs

Several 'linear time' statements do not measure bit operations, and the input threshold is not accounted for in the stated size convention.

An arbitrary binary g can have more bits than the number of tetrahedra. Even if there are O(t) normal arithmetic tests, they act on binary integers, and applying the orbit theorem supplies a polynomial bound, not a linear bound for the orientation test. Also, the boundary-component reference is to the surface corollary even though the boundary input is a normal curve.

Measure the input by the encoded triangulation, knot and threshold length. Use normalcurvecount on the boundary, and state polynomial bit bounds for all operations. If a self-contained NP verification of integral null homology is desired, add an integral 2-chain certificate solving the simplicial boundary equation. To see its bit bound, choose r independent columns and r rows giving a nonsingular minor of the boundary matrix, with absolute determinant D. Starting from any integral solution, reduce each nonpivot coefficient modulo D and compensate in the pivot columns: D times every other column is an integral combination of pivot columns by the adjugate formula. The remaining pivot coefficients are obtained from the chosen rows by Cramer's rule and have polynomial bit length by determinant bounds. The verifier need only check the chain equation.

These are repairable complexity and specification issues. They do not justify the printed linear bit bounds, but do not obstruct the polynomial bound with the conditional inputs.

T4

Checked statement: Theorem 19: NP-hardness for the metrized PL minimal-spanning-area decision problem, including the allowed surface and cell types, separation at an integer threshold, and polynomial-bit metric data.

Returned assessment: repairable_gap

A new repair gives a strict gap for embedded orientable PL spans, and its lower bound also holds for continuous spans with area measured by the two-dimensional Hausdorff area of their image. First use the mod 2 relative-chain argument from T2, without any genus estimate. For any map into B that takes its single boundary homeomorphically to K, F₀ has coefficient 1, exactly one literal page per variable has coefficient 1, and each clause has one or three coefficient-one incidences. Every interior point of such a page must be covered: the relative chain maps to the nonzero generator in the local homology at that point, which would be zero for a map missing the point. Thus, with one disjoint marked disk of area at least 1 per literal occurrence, every mapped span covers at least m marked disks, and an unsatisfiable instance forces at least m+2 whenever a span exists. For the 3D lower bound, fold the double and project to B. These maps are nonexpanding for the induced path metrics: they are nonexpanding in every product cell and the maps agree on the glued interfaces, so the length bound follows by taking the infimum over cellwise paths. A 1-Lipschitz map cannot increase two-dimensional Hausdorff area, by the diameter-cover definition. On the interiors of the flat triangles the measure is ordinary Euclidean area; their edges have area zero. Thus the same lower bound holds for embedded PL surfaces upstairs, including surfaces not lying in any selected page section. For parametrized PL area with multiplicity the lower bound also follows, since multiplicity can only increase the area over that of the image. No least-area existence or strict projection theorem is required. For explicit rational metrics, take the linear-size triangulation of T2, with one designated interior triangle per occurrence (insert constant-size triangulated patches if needed). Let T be the number of triangles before replacement, m≥1, and ε=1/[100(T+m+1)]. Set all original triangle sides to ε. Replace each designated triangle with a disk of three isosceles triangles about a new center, retaining the perimeter lengths ε and assigning each spoke length L=(2/(3ε))(1+1/(8m)). The area of this disk is (3ε/2)√(L²−ε²/4)=√((1+1/(8m))²−9ε⁴/16), strictly between 1 and 1+1/(8m). The remaining triangles have total area at most Tε²/2. Use right product prisms: height h=ε/100 on literal products and five layers of height h on F₀. Glue equal base-edge lengths and equal port heights by isometries and double. No diagonal lengths of tetrahedra are needed. Put K at height zero on the unglued boundary of the central product. A satisfying assignment gives the embedded span of T2, horizontal on each selected literal with heights prescribed on the boundary circles of F₀. Interpolate heights linearly on its equilateral triangles, using values in [0,5h]. The gradient has norm at most 20h/ε (bound its two components using the base and altitude of the triangle), so graph area there is at most twice base area. Exactly m marked disks are used; total area is less than m+1/8+Tε²<m+1. Take C=m+1, so both <C and ≤C are separated from the no-case bound m+2. Empty clause lists can be sent to a fixed yes-instance. There are O(T) cells and all displayed lengths have O(log(T+m+2)) bits. If integer lengths are required, multiply by a common denominator and rescale C by its square; the bit length remains polynomial.

Premises used

  • The problem definition permits right triangular prisms with rational edge lengths and isometric face gluing.
  • The same conditional Schaefer hardness input and historical source record as in T2. No genus-to-area comparison theorem or least-area existence theorem is imported.

Missing inputs

  • Verification of the cited external hardness input, as in T2. If a different area or surface class from embedded PL spans is intended, its definition must be specified before asserting that broader formulation.

Scope changes

  • State the problem as existence of an embedded orientable PL span, not as existence of an attained optimum; the repair also gives the stated lower bound for continuous spanning maps with image area.
  • The repair works for both strict and non-strict threshold versions, on closed orientable metrized outputs with rational right-prism cells.
  • No NP upper bound or exact area computation is asserted.

Located concern

AHT-TeX, section 7, paragraph beginning 'We saw in Theorem'; AHT-p27

The genus argument does not give the claimed area converse. A minimum-genus span is not shown to use exactly one disk per clause in arbitrary instances, nor need a small-area span satisfy a genus bound.

Lemma 6 only forces one selected occurrence under the genus bound n+m. In contrast, the parity equations for an arbitrary map allow three selected occurrences in a clause. This possibility cannot be excluded just by supposing there is some spanning class. For example, use the positive clauses (x,x',y), (y,y',w), (x,a,b), (x',a,b), (y,c,d), (y',c,d). The last four force x=x' and y=y' on Boolean assignments; the first then forces x=0,y=1, making the second impossible. Yet there is an integral signed solution with x=x'=0, y=y'=1, w=−1, a=1, b=c=d=0. Assign these coefficients to positive pages and their complements to negative pages and give F₀ coefficient 1. Their oriented boundaries cancel except at K. The signed chain can be lifted to the thickening by adding vertical annuli over the seams, so even integral null homology does not rule out this type of no-instance.

Use the new relative mod 2 local-degree area lower bound above for every spanning surface, independently of genus.

The printed no-direction is missing; the repair supplies a quantitative gap even after the thickening and doubling.

Located concern

AHT-TeX, section 7, final two paragraphs; AHT-p6, Figure 2

Nonincrease under projection is not a proof that an embedded minimizer exists on B or that an explicitly chosen embedded span is least-area.

Projection preserves area on horizontal patches and can identify different sheets. The product projection on the port construction also has no section across an entire branching seam that meets all page interiors: approaching the seam from different literal pages puts the limits in disjoint ports. Neither the area inequality nor the fact that an abstract branching surface can be pictured inside a thickening supplies an isometric embedded lift of a projected span.

Use folding and projection just for a lower bound, and explicitly lift satisfying choices by the small-gradient graph construction. Remove the claims about strict decrease and attainment, which are not needed for hardness.

The printed minimizer inference is unsupported. The repaired reduction proves existence below the threshold for yes-instances and exclusion for no-instances, not a statement about the location or uniqueness of minimizers.

Located concern

AHT-TeX, section 7, metric definition, problem box, and metric construction; AHT-p27, Figure 5

The rational metric construction and its bit bounds are asserted without details, and the problem switches between <C and ≤C.

Figure 5 is explicitly not to scale. It does not give side lengths realizing a large marked disk with a small perimeter. Nor does subdividing a rational right prism into Euclidean tetrahedra in general keep diagonal lengths rational. The boxed question uses ≤C, whereas the surrounding prose uses <C; an equality instance can distinguish them.

Use the explicit isosceles disks, unsubdivided metric right prisms, and strict separation above. Include cell and gluing incidence data and the knot in the input encoding as well as lengths and threshold.

Neither finite precision nor the strictness choice obstructs the repaired reduction. The metric construction and size are not established by the illustration alone.

T5

Checked statement: Logical assembly of Theorems 1–3 and interpretation of the general-manifold and S³ problem classes and the two section 8 questions.

Returned assessment: no_issue_found

Theorem 3 is exactly the conjunction of NP-hardness and NP membership for the same bounded-genus language on variable triangulated orientable ambient manifolds, with the knot in the 1-skeleton. The logical implication checks; it inherits, rather than resolves, the proof obligations of T2 and T3. The reduction's varying ambient manifolds provide no NP-hardness result for S³ or for any fixed ambient manifold. The upper-bound verifier can be used under the promise that the supplied triangulation has the stated ambient type, or with an encoding giving a suitable triangulation by a polynomial-size conversion; an arbitrary-input recognition condition for that type is a different requirement. Section 8 question 1 asks about hardness with the S³ restriction and is not answered by these arguments. Question 2 uses 'determining the genus is NP' as shorthand for an NP certificate of a lower bound, not the already studied upper bound. With finite integer thresholds, the complement of g(K)≤g is g(K)≥g+1, including nonspanning knots with genus ∞. A lower-bound NP verifier on the full input class of Theorem 3 would therefore put that NP-complete upper-bound problem in coNP and imply NP=coNP, conditional on Theorem 3. At threshold zero it would in particular give nontriviality certificates for classical knots. Upper and lower certificates together would also certify a claimed finite exact value. These are implications about decision versions, not a claim that a numerical output function belongs to a decision complexity class.

Premises used

  • Theorems 1 and 2 must apply to the same binary-threshold decision language; Theorem 3 uses both.
  • The problem convention g(K)=∞ in the nonspanning case.
  • Elementary complement and threshold-shift relations for integer genus. No later complexity result about classical knots is imported.

Missing inputs

  • The unresolved witness and algorithm premises identified in T1 and T3 and the external source-problem premise in T2, if Theorem 3 is to be certified rather than its logical assembly checked.

Scope changes

  • Separate the arbitrary-manifold language from the S³ restriction and from recognition of the ambient manifold in an unrestricted encoding.
  • Treat question 2 as a lower-bound decision problem (and distinguish it from exact numerical output).
  • The assessment is historical and does not assert the present-day status of either open question.

Outside the audit

  • Full correctness and complexity of the general unweighted interval algorithm, beyond the particular normal-arc encoding and conditional use checked in T3.
  • The weighted orbit-counting algorithm and the component-topology corollaries of section 6.
  • The full contents of the external references and incidental historical and complexity claims outside the assigned targets.
  • Post-cutoff developments and the current status of the open questions.
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}
}