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-astra high: aht-progress-challenges

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.

Both progress objections are substantive. The first falsifies five-cycle progress and every constant-times-k halving bound for the stated potential; the second falsifies the telescope's application across full cycles, with one incorrect merger remark in the candidate account. Neither refutes correct orbit counts, gives a superpolynomial lower bound, or refutes knot genus in NP. The printed polynomial-time proof is incomplete. A changed unweighted schedule admits a polynomial amortization and can replace the affected subroutine without assuming a normal-surface restriction.

P1

Checked statement: For the printed cycles and reference-endpoint rule, Claim 3 gives five-cycle progress, and the width potential halves within a universal constant times k cycles.

Returned assessment: claim_false

Use inclusive widths and count the two sides of each pairing. Initially the support is [D+1,2W+D]. Deleting [1,D] changes the active right endpoint to 2W, not the reference Z=2W+D. With A=W-D, the pairings now have sides [A,2W-1], [A+1,2W] and [1,W], [W+1,2W], respectively. Neither needs trimming, there is no second increasing pairing to merge, and the increasing g uniquely wins on range width. For a translation by t>0 with range starting at c, an eligible side starting at u is shifted back by (1+floor((u-c)/t))t. Thus g shifts just the range of h back by D+1, to [A,2W-D-1]. Truncating g to this latter right endpoint gives N1=2A-2+(D+1); h now acts by x ↦ N1+1-x. In general the state at the end of cycle j is N=2A-2+E, g:[A,N-1]→[A+1,N] increasing, h:[1,N-A+1]→[A,N] decreasing. For E≥3 there is no static interval. The next trim of h leaves [1,q] paired to [N+1-q,N], q=floor(N/2)=A-1+floor(E/2), including the omission of the fixed midpoint when there is one. Its range now starts at A+ceil(E/2)>A+1. Step (4) still cannot merge; step (5) uniquely selects g. It shifts just the range of h by -ceil(E/2), until its start is A. The reflection constant drops by the same amount, and precisely this much terminal suffix is truncated from g. This gives the asserted state with E replaced by floor(E/2). In particular E_j=floor((D+1)/2^(j-1)) through E_s=2 for D=2^s. Normalizing a transmitted pairing by inversion causes no change to this calculation. In the end-of-cycle state h, not g, has the wider range at N; this fact does not determine the winner after the next trim.

With Δ=2w-(Z-u+1) for a side starting at u, substitution gives, in order g-domain, g-range, h-domain, h-range, Δ=(W-4D+2E-5, W-4D+2E-4, 2E-3D-2, W-4D+2E-3). For W≥8D and 2≤E≤D+1 the signs are (+,+,-,+). Initially the h-domain has margin zero and the other three margins are positive. Thus, for example, cycles 2 through 6 give five complete cycles with three close intervals both before and after, and k=2 throughout. Switching from weak to strict closeness does not save the claim. Alternatively start at the state on [1,2W] before the first transmission, with Z=2W. The same recurrence holds without any contraction; the end-of-cycle margins are the displayed margins plus D. The h-domain margin is zero at cycle 1 and negative thereafter, all others positive. The weak count starts at four, is still four at cycle 1, then is three; the strict count stays three. One can choose s large enough for a five-cycle block entirely in the constant part. Restarting Z afresh at the start of every test block would be a different test; its decreases cannot just be chained using 1218-1225.

The potential is X0=16W(W+D) and X_j=16(A-2+E_j)(A-1+E_j), nonincreasing on this prefix. The ratio at s is (W-D)(W-D+1)/(W(W+D))≥(1-1/8)^2/(1+1/8)=49/72. Taking s>2C defeats halving within Ck cycles, not just the particular constant 5. For W=32768, D=4096 the formula gives (N,X)=(57598,13387878432) at j=5 and (57350,13159301792) at j=10, versus X0=19327352832. No empirical extrapolation is needed.

Even the end of the run is benign. At E=2 the active size is 2A. After trimming, both ranges are [A+1,2A], and h wins the domain-start tie (1 versus A). It sends the range of g to [1,A]; after normalization g is a reflection [1,A]→[A,2A-1]. Truncation leaves h:[2,A]→[A+1,2A-1]. In the next cycle trimming g makes its range equal to that of h, and now g wins by its smaller domain start. Transmission turns h into the unit shift [1,A-1]→[2,A], and truncation deletes g. One further truncation removes the shift, leaving one static point. This gives s+3 truncating cycles under the lexicographic rule. In the original input the shift connects [W,N0] and h attaches the rest of [D+1,N0] to it, so the answer is indeed D+1 including the initial isolated points.

Premises used

  • Z is fixed between decreases of k, as in AHT-original 1218-1225.
  • Step (5) follows the trim and merger search. The suffix to truncate must lie in the maximal range, as required by 943-954, 958-968.
  • The lexicographic refinement at 793-797 matters for the stated cleanup trace but no tie-break is needed in the long prefix.
  • The displayed proof uses symbolic endpoint calculations. The prefix checker's maximal inverse power, normalization and suffix computations agree on these prefixes; its assertions are not execution results.

Missing inputs

Scope changes

  • These are counterexamples for the interval-system algorithm, not examples of an incorrect orbit count.
  • The tail calculation uses the paper's more precise maximality order; allowing arbitrary ties in the shorter description of maximality cannot remove the prefix counterexample.

Located concern

AHT-original 1261-1269, 1286-1319

The next cycle need not transmit the previously selected maximal pairing. Disjointness after a trim also does not, with weak closeness, always make the trimmed domain non-close.

In the recurrence h overtakes g at the right endpoint and loses to it after trimming. For the weak-closeness boundary case alone, [1,W] paired to [W+1,2W] has disjoint sides but [1,W] is 2W-close.

Distinguish cycles from changes of selected pairing. Strict closeness removes the abutment equality but does not fix the five-cycle statement. A change of algorithm with proved progress is described under P3.

Claim 3 is false as a progress assertion for complete printed cycles.

Located concern

AHT-original 1205-1207, 1428-1440

Neither the number of sides counted nor a constant multiple of k as a halving time is justified.

There are up to 2k close sides, not k. More importantly, k=2 and X_s/X0≥49/72 for unbounded s.

Correct the side count, but replace rather than rescale the halving argument.

The stated amortization fails. The long phase here is only logarithmic in N, not evidence of a superpolynomial running time.

P2

Checked statement: With the printed Z convention, disappearance of close intervals across complete cycles forces a halving as used in the application of Claim 4; initially disjoint sides might exclude the reflection obstruction.

Returned assessment: claim_false

For N=Z=29 the sides initially cover [1,29]. The first winner is h, ending at 29, and g's range [15,25] is not inside [17,29]. There is no merger (h has t=16>w=13). Truncating [26,29] leaves h:[1,9]→[17,25] and g:[14,24]→[15,25]. X falls from 2288 to 1584. The only static interval is now [10,13]. Closing it up gives N=21, h:[1,9]→[13,21], g:[10,20]→[11,21]. The former has t=12>w=9 and cannot merge. The latter wins on width, sends the h-range three places left to [10,18] and leaves the h-domain unchanged. Truncation leaves g:[10,17]→[11,18]. Thus X=16·8·9=1152>1144=X0/2. With Z still 29 the margins are -4,-3,-11,-2. Both cycles satisfy the actual order of operations, the first truncation started with d1=Z, and no close side remains. In particular a proviso that static points have already been removed at initialization is insufficient.

The specific failed telescoping identification is d_i'=d_(i+1) at 1341, 1356: here the endpoint 25 at the end of truncation 1 is 21 when the next truncation starts. There is a valid narrower calculation. If k stays fixed, the first maximal range ends at Z, successive truncated endpoints are the next maximal endpoints without renumbering, and the next range at that endpoint contains the shortened one, write c_i for the range starts, w_i,w_i' for the pre/post widths. Then c_(i+1)≤c_i and w_i'/w_(i+1)≤(Z-c_i+1)/(Z-c_(i+1)+1), by evaluating the increasing ratio (x-c_i+1)/(x-c_(i+1)+1) at x=d_i' and at x=Z. Multiplication bounds the product of truncation factors by w_r'/(Z-c_r+1). If the last range is not weakly close this is <1/2. Other operations that only preserve or reduce the width product do not invalidate this upper bound if the endpoint hypotheses hold. The example disproves the complete-cycle application, not that conditional inequality.

For the lift, put n=N0, add the shift T by n from [1,n] onto [n+1,2n], and add n to the output of each original map. Every pairing joins different blocks, T covers both blocks, and the shifted increasing g has distance n+1 greater than its width. The shifted h reverses orientation with disjoint sides. No merge or trim precedes selection. T has strictly wider range than either competitor ending at 2n. Each competitor has just its range transmitted, exactly once, reproducing its original map. The terminal block is now exclusive to T and is all its range, so truncation deletes T and k drops from 3 to 2, with N and the reset Z both n. This proves the lift assertion for interval data.

Premises used

  • A complete cycle may include a contraction before its truncation, without a decrease of k.
  • Periodic merger requires the overlap-width test at AHT-original 859-864, not merely periodicity of both pairings.
  • Disjointness in the lift means each individual domain is disjoint from its own range; the domains of different pairings need not be disjoint.

Missing inputs

Scope changes

  • The verdict concerns the application across full cycles and the proposed disjointness defense, not the pure telescoping inequality.
  • The shifted 30-point presentation is unnecessary; its first contraction produces the same coordinates as the start of the 29-point calculation but with reference 30.

Located concern

AHT-original 1338-1344, 1354-1362, 1431-1435

The telescope uses a common coordinate system at consecutive truncations, without securing it across contractions.

The 29-point trace loses all close sides with no k drop and with 2X_final-X_initial=16>0.

Restrict the telescope to the stated endpoint hypotheses, or justify new charges for renumbering. In the modified algorithm under P3 there is no interior renumbering.

Claim 4 is false if meant to cover these cycles; if it means only a compatible series of truncations, the inference to cycles is invalid.

Located concern

candidate-progress-objections 619-621

The suggested availability of a merger after transmission 2 is incorrect.

After transmission the spans are [10,21] and [1,18], periods 1 and 9, so the overlap [10,18] has width 9, not at least 10. Shortening the first span to [10,18] does not improve this.

Say that h becomes periodic, but the two pairings still fail the merger test. No appeal to deferral of an available merger is needed.

This corrects the candidate explanation without weakening the counterexample.

Located concern

candidate-progress-objections 636-672; AHT-original 1471-1483, 1526-1541

Disjoint initial sides are not an invariant excluding the bad states, but neither is the two-block construction a normal-coordinate construction.

One lift cycle recovers the overlapping g exactly. No triangulation, matching data or compatible elementary disks are specified by that lift.

Keep the assertion at the level of interval systems. A restricted-input defense of the printed analysis would require an additional proved property of reachable states.

Initial disjointness alone is defeated; normal-surface realization is not decided.

P3

Checked statement: Theorem 12's polynomial bound for the exact printed algorithm, possible repair of polynomial orbit counting, and consequences for the knot-genus verifier and hardness result.

Returned assessment: unresolved

For the literal six-step algorithm the progress objections leave the polynomial cycle bound unresolved, not disproved. Orbit correctness is a separate argument: removing identities and redundant reflected edges does not change the equivalence relation; a merger substitutes the same congruence classes on the combined span; a transmission replaces a generator by a composite with the retained generator and can be undone using that generator. An exclusive terminal suffix has paths back to retained representatives by the maximal inverse pairing (iterate for a translation); its removal cuts off terminal parts of shift chains, or leaves of trimmed reflected pairs, without separating retained representatives. Static points each count for one orbit. Here and below truncation means the suffix within the maximal range and pairings are normalized after transmission. In a nonterminal printed cycle, after transmission no competitor still ends at the active right endpoint: an ending range was eligible, and an unshifted side reaching that endpoint could not have extended left of the maximal range while having at most its width. Thus truncation makes progress. This gives the elementary O(N) cycle bound, with polynomial bit cost per cycle using division for maximal powers, interval operations, and gcds. It does not give a polynomial in the input bit length.

There is a repair for the orbit-counting problem by changing the schedule. A proof is given in the second issue below; in particular it does not assume a bound on runs of the printed schedule. With this substitution, the affected polynomial-time step in the NP certificate can be supplied. Corollary 13 constructs at most 3t arc pairings and Corollary 14 at most 12t, with orbits equal to components (disk boundaries connect the corners of each elementary disk). Their constructions, not the complexity proof for general pairings, give these special input bounds. Use N equal to the number of edge intersections; if W denotes the sum of disk coordinates rather than intersection weight, N≤4W suffices, and similarly N≤2W for arcs. Neither corollary itself bounds cycles on its special inputs. The verifier uses unweighted counts for F, its boundary curve, and the normal surface with coordinates 2v(F); for connected F in an orientable ambient manifold the latter is the normal-side double cover and distinguishes one-sided from two-sided F. It is polynomial, not necessarily linear, time that is needed. The verifier separately checks admissible coordinates, boundary essentiality and Euler characteristic, and uses a fundamental minimal-genus witness and the bound on its coordinates. With t denoting exterior triangulation size (only a constant-factor subdivision overhead), the supplied bound gives N≤28t²·2^(7t+2), hence polynomial log N even for the doubled test. That size bound alone could not turn O(N) cycles into a polynomial verifier. Subject to the other normal-surface and certificate premises of the paper, the substitution restores this use without requiring any running-time theorem for the exact printed cycles. The section 3 NP-hardness proof instead constructs the branching surface from ONE-IN-THREE SAT, thickens and doubles it with polynomial triangulation size, and uses the spanning-surface/assignment equivalence. It does not import any interval-algorithm complexity assertion.

Premises used

  • Binary interval endpoints and orientations, the elementary orbit equivalences, and the periodic merger criterion of AHT-original 858-877.
  • For the verifier implication, the other topological and witness-size inputs in AHT-original 369-396 and 1616-1721 are taken as supplied, not re-proved by the progress analysis.
  • A polynomial-time replacement for unweighted orbit counting suffices for the knot-genus verifier; matching the printed sequence of intermediate pairings is not a verifier requirement.

Missing inputs

  • For a polynomial-time conclusion about the exact printed schedule: a cycle analysis valid with its actual trim order and contractions, or a different proof bounding that schedule.

Scope changes

  • The unresolved verdict is for the running time of the exact original algorithm. The proved replacement deliberately changes both the treatment of interior static gaps and the timing of trims/transmissions.
  • The NP-completeness conclusion combines separate membership and hardness arguments; this audit of one subroutine is not a fresh verification of all the topology in either argument.
  • The weighted extension at AHT-original 1962-2001 imports a cycle bound and adds weight-list overhead; it is not used by the NP verifier. The later application at 2014-2049 supplies its own bounds on k, m and d, and 2060-2069 bounds log W for fundamental input. No weighted-algorithm repair is needed or claimed here.

Located concern

AHT-original 1190-1209, 1255-1320, 1426-1443; candidate-progress-objections 674-694

Counting runs instead of cycles is not by itself an amortization.

The family in P1 has logarithmically many selections of the same winner while its width product barely changes when W=D². P2 defeats a separate inter-cycle telescope. Neither trace is slow enough to refute polynomial time.

For the unchanged algorithm one would still need bounds on time inside runs, progress between runs, and renumbering or resets. No such complete proof for that algorithm is claimed here.

The printed complexity proof is incomplete while its progress assertions in the specified scopes are false. Failure of NP membership or of NP-hardness does not follow.

Located concern

Repair to the schedule of AHT-original 1131-1157 and the analysis at 1211-1443

A replacement must ensure that a surviving truncated pairing is actually transmitted at the next change of maximal pairing, and must preserve coordinates through a halving argument.

The delayed trim in P1 defeats the first condition, and closing an interior gap in P2 defeats the second.

Use the following modified unweighted algorithm. Keep interior static points in place. Delete and count only uncovered terminal suffixes (count the whole remainder if there are no pairings). Keep the system normalized, trimmed and free of identities. At the start of a step do an available periodic merger and restart if there is one. Otherwise select the widest range ending at the current endpoint n, belonging to Q with range [c,n]. Hold Q fixed. For each other pairing P with range contained in [c,n], transmit by the usual maximal inverse powers, normalize, trim at once if necessary, and repeat on P while its range is contained. Delete identities; a deletion can restart the step. When all other ranges start strictly left of c, truncate Q by the maximal exclusive suffix. Call this entire fixed-Q operation a macro step. All operations are among orbit-preserving moves or counted deletions of isolated points. In particular, leaving static points until they become terminal does not affect their eventual count.

(1) Cost of stabilization with Q fixed. Immediately after a transmission, before any new trim, both side starts of P are <c: any side not shifted started <c, and a shifted side has passed that threshold (for a trimmed reversing Q its image even ends before c). Only a trim can require repetition. If Q reverses, then on a repetition the new trimmed reflection has domain starting <c, so only its range moves, turning it into a translation, and there is no further repeat. For an increasing Q, consider a repeat caused by trimming a reflection x ↦ H-x. Its trimmed range starts at u=floor(H/2)+1≥c and its domain starts <c. Moving just the range left by m shifts the reflection constant to H-m, unaffected by normalization and retrimming. Here m≥u-c+1. The nonnegative excess e=H-2c+2 at a repeat therefore goes to at most ceil(e/2)-1 if another repeat occurs. Since H≤2N, this gives O(1+log N) transmissions per other pairing. After stabilization no other range can still end at n: any initially eligible competitor had width at most that of Q, never enlarged, and now starts <c; others ending at n could not have been ineligible by maximality. Thus truncation deletes at least one point. If Q survives and k does not drop, its shortened range ends at the endpoint of another range starting strictly left of c. Without a merger the next maximal pairing is therefore different, contains this shortened range, and transmits it. There is no static suffix to remove in between and no pending trim.

(2) Halving test. Consider a block starting with reference Z equal to the current right endpoint of the first maximal range, after terminal cleanup. End the block upon a k drop or halving of X. At constant k, write c_i,w_i,w_i' for the range start, pre-width and post-width of the ith truncated maximal pairing. Apply the telescope proved under P2: the endpoint is unchanged between consecutive selections and c_(i+1)<c_i. Extra trims only reduce the product. Thus X_after/X_start ≤ w_r'/(Z-c_r+1) after truncation r. In particular a post-truncation maximal range failing strict closeness, 2w>Z-u+1 for a side starting at u, suffices for halving. A k drop also suffices: deletion loses a factor at least 4, and in a merger the new width is at most w_1+w_2≤2w_1w_2 (the span overlap is at least the sum of periods). All intervening moves are nonincreasing for X.

(3) Bound on macro steps per block. For fixed Z the number of strictly close sides cannot increase at constant k. Indeed strict closeness is width > distance from the right end of the side to Z. Restriction cannot make a non-close side close, nor can an inverse shift left; inversion for normalization just exchanges side names. Suppose there is no block end, so each truncated maximal range stays strictly close. In a sequence with no decrease of close count, the next maximal Q transmitting that range J must be increasing: J's inverse image must stay close, but the domain of a trimmed reverser of width v has at least v places to its right and cannot be strictly close. Moreover Q's domain contains the close image, hence is close, and remains so through truncation if there is no count loss.

Here is the merger check needed for two consecutive such transmitters. The first transmitter P now has both sides close after its truncation. The second transmitter Q, also increasing, transmits P's range J, of width w and start j, by r≥1 inverse shifts of size t, producing start j'=j-rt≥a, where a=c-t is Q's domain start. The resulting increasing P has side starts L≤R<c, one of them j'. Its sides remain close and have width w; there is no retrim. If L=R there is an identity deletion. Otherwise P is periodic, of period R-L: two equal-width strictly close intervals in [1,Z] have starts differing by <w (the later interval fits before Z and the earlier has width greater than its right-hand gap). Likewise Q is still periodic after truncation because both its equal-width sides remain close. J and the side starting at L were strictly close relative to the same Z, so w>j-L. Since L≤j' and j≥a+t, this gives w≥t+max(0,a-L). After truncating Q its upper endpoint still covers R+w-1. Its periodic span starts at a, so the two spans overlap in width R+w-max(L,a)≥(R-L)+t. This is the actual merger test, with the single period t, even when r>1. A merger must be available at the next step.

Consequently four consecutive macro steps with no block end and no close-count loss are impossible: after the first truncation, steps two and three would supply the consecutive transmitters just analyzed, forcing a merger before step four. There are at most 2k side losses per fixed-Z block. This yields O(k+1) macro steps per halving or k drop. Start a fresh reference at the next block; this reset is paid for by the preceding halving. Initially X≤(4N)^k and X≥1, giving O(k(1+log N)) blocks. Selection, merger searches, suffix accounting, and the O(k(1+log N)) transmissions/trims per macro step use polynomially many bit operations on O(1+log N)-bit endpoints. This proves polynomial time for this modified schedule on arbitrary signed interval pairings.

This is a deterministic repair of the existential unweighted polynomial orbit-counting bound and hence of the affected verifier subroutine. It neither proves the literal Theorem 12 cycle bound nor vindicates Claims 3 and 4 for the printed cycles.

Located concern

AHT-original 1456-1555, 1671-1694, 1712-1721

The small number of pairings and polynomial witness bit length in the applications do not themselves bound the number of printed cycles.

The interval length, even with a fundamental witness, is bounded exponentially rather than polynomially in the number of tetrahedra. Conversely the examples attacking the cycle proof do not supply bad normal-surface instances.

Use polynomial orbit counting as a subroutine, for instance the modified schedule above, with the boundary tested by the normal-curve construction. Only polynomial time is claimed for those tests.

The NP upper-bound argument needs an efficient component test, not this particular amortization. The NP-hard lower bound has no such dependency.

Outside the audit

  • No journal-version collation, external literature check, program execution, or inspection of an unsupplied companion program.
  • No general lower bound or polynomial upper bound established here for the exact original cycle schedule, and no realization of the witnesses by compatible normal coordinates.
  • Independent topology, minimal-spanning-area arguments, and correctness and detailed complexity of the weighted extension beyond the dependency distinctions stated above.
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}
}