About the problem

Update (2026-07-31): We have removed this problem from the benchmark because we determined that the verifier would not detect correct solutions with high enough fidelity.

The unknotting number of a knot is a classic invariant. It is defined as the smallest number of crossing changes required to change a diagram of the knot into a diagram of the unknot. This problem is to devise an algorithm that decides whether a diagram depicts a knot with unknotting number one.

This problem is one of the fundamental questions in low-dimensional topology and a solution would be a major result. The problem sits at an interesting point in terms of complexity: while there are algorithms for determining if the unknotting number of a knot is zero, the general problem of determining the unknotting number of a knot is not even known to be decidable. The problem author is optimistic that the case of unknotting number equal to one is at least decidable, and even computationally manageable for diagrams of moderate size.

Rather than attempt full theoretical verification, we test proposed algorithms on a hidden challenge set of knots with known unknotting numbers. While we hope that perfect performance on this challenge set would be indicative of a conceptual breakthrough, it is possible that an AI system will throw together many ad hoc approaches and succeed. If so, we may repair the problem by generating still more challenging examples.

Read more here.

Prompt

Produce an algorithm that takes as input a diagram of a knot and returns True if the unknotting number of the knot represented by that diagram is 1 and False otherwise. For a knot with up to 100 crossings, the algorithm must complete in under an hour when run on a typical laptop.

Provide your solution as a self-contained Python script. Accept 1-indexed planar crossing diagrams as the input format.

Example input: [[4,2,5,1],[10,6,11,5],[8,3,9,4],[2,9,3,10],[11,16,12,17],[7,15,8,14],[15,7,16,6],[13,20,14,21],[17,22,18,1],[21,18,22,19],[19,12,20,13]]