Just now, Claude independently solved a graph theory conjecture in only 31 steps, which shocked Donald Knuth, the father of algorithms, and made him issue a statement.
[Introduction] Just now, Claude independently solved a graph theory conjecture, leaving Donald Knuth, the computer titan who wrote The Art of Computer Programming, completely shocked! This time, AI has reached a new milestone in automatic reasoning and solving creative problems.
Shocked! Shocked!
Just now, Claude independently solved an unsolved graph theory conjecture problem in just 31 steps.
Donald Knuth, the godfather of algorithms who wrote The Art of Computer Programming, exclaimed, "I have to re-evaluate the role of generative AI in mathematical research."
On the official website of Stanford University, he published an original paper. The first two words of the paper are "Shock! Shock!"
Paper link: https://www-cs-faculty.stanford.edu/~knuth/papers/claude-cycles.pdf
Who is Donald Knuth?
He is the Turing Award winner who wrote The Art of Computer Programming (TAOCP) and invented TeX, and is regarded as the godfather of the algorithm field.
The Art of Computer Programming is the most important project in Donald Knuth's life. The purpose of writing this book is to "organize and summarize the relevant knowledge of computer methods he knows and lay a solid mathematical and historical foundation."
If a person who has written algorithm books for 50 years starts to seriously consider the mathematical ability of AI, it means that AI is entering the most core intellectual field of humanity.
The problem that stumped the godfather of algorithms was solved by Opus 4.6
At the beginning of the paper, Donald Knuth wrote:
I learned yesterday that an unsolved problem I had been working on for weeks was just solved by Claude Opus 4.6, a hybrid reasoning model released by Anthropic three weeks ago!
He said bluntly:
It seems that I have to re-examine my view of "GenAI" sooner or later. It's really delightful to learn that my conjecture not only has a beautiful solution but also to witness this dramatic progress in automatic reasoning and creative problem-solving.
The story goes like this. The The Art of Computer Programming series started to be written in the 1960s, and now five volumes have been published.
At the age of 88, the godfather of algorithms is still writing this series of books.
He prepared a problem about directed Hamiltonian cycles in the book. He and his friends proved a special solution to this problem, but they couldn't generalize it to the general case.
As a result, this problem was solved by Claude Opus 4.6.
More precisely, AI found a beautiful construction method, and Donald Knuth then gave a rigorous mathematical proof.
This paper has thus become a landmark event - generative AI is recorded in the story of mathematical research for the first time.
What does the problem that stumped the godfather of algorithms look like?
This problem is a graph theory problem that looks simple but is actually very complex.
First, imagine a three-dimensional grid space, such as an m×m×m cube.
Each point in it can be represented by three coordinates (i, j, k), and each coordinate ranges from 0 to m - 1. So, there are a total of m³ points in the entire space.
Next, we stipulate that from each point, we can move in three directions: increase i by 1, increase j by 1, and increase k by 1. If it exceeds m - 1, it starts from 0 again. This forms a circular space.
According to the formal definition in Donald Knuth's paper, each vertex has three directed edges, pointing to the "next" vertices in three directions respectively.
Therefore, the entire graph has m³ vertices and 3m³ directed edges.
A Hamiltonian cycle is a path that passes through all vertices exactly once and then returns to the starting point. This is a classic graph theory problem.
The problem proposed by Donald Knuth is even more difficult: instead of finding one route, we need to find three routes, and each route is a Hamiltonian cycle, each with a length of m³, and the three cycles just cover all the edges.
That is to say, each edge can only belong to one of the cycles.
Originally, Donald Knuth was going to write this problem into a new chapter of The Art of Computer Programming.
Why is this problem so difficult? The reason is that each point has three outgoing edges. If we want to form a Hamiltonian cycle, we must choose one of them. So at each point, we need to make a choice.
Therefore, the problem scale reaches 3^(m³)! It is almost impossible to complete this through brute-force search. Therefore, we must find some regular construction methods.
Previously, Donald Knuth had solved the case of m = 3, and his friend Filip Stappers found solutions for 4 ≤ m ≤ 16 through experiments.
This shows that the answer probably exists!
So, can we find a general formula?
Multiple attempts: Claude is doing research
Filip gave the problem to Claude Opus 4.6 and set a strict rule - after each run of the program, the progress of the exploration must be recorded.
Interestingly, Claude didn't have a sudden inspiration but went through 31 explorations. The process is very similar to a graduate student doing research.
In the first step, it tried simple functions and attempted to use a function g(i, j, k) to determine the direction of each point. But soon it found that simple linear functions didn't work.
In the second step, it started a brute-force search and tried to use depth-limited search (DFS), but the search space was too large and the efficiency was too low.
In the third step, it did a two-dimensional analysis. Claude found that if we only look at the two-dimensional case, we can find a "snake-like path". So, it tried to generalize the two-dimensional idea to three dimensions.
Subsequently, it constructed a three-dimensional snake-like path similar to the Gray code, but after deleting the first path, the remaining structure was difficult to decompose.
In the next dozen or so explorations, Claude basically kept making trial and error.
Key breakthrough: Fiber decomposition
In the 15th exploration, Claude proposed a key idea: fiber decomposition.
It noticed that if we define s = (i + j + k) mod m, then all edges will move vertices from s to s + 1. This means that the entire graph can be divided into a layered structure by s.
In this way, each layer is like a two-dimensional grid, which greatly simplifies the problem.
Claude then tried random search, simulated annealing, and backtracking search. These methods could find some solutions, but still didn't discover the general rule.
So Claude concluded that a pure mathematical structure was needed.
In the 31st exploration, Claude found the rule
In the 31st exploration, Claude finally proposed a set of simple rules, with the core still being s = (i + j + k) mod m.
Then, according to the values of s, i, and j, it determines whether to increase i, increase j, or increase k. This is called the "bump" rule in the paper.
The rules are roughly as follows: If s = 0, the moving direction is determined by the value of j. If 0 < s < m - 1, it is determined by the value of i. If s = m - 1, another rule is used.
In this way, a complete path is generated.
Claude verified with a program that for m = 3, 5, 7, 9, 11, the paths are all valid. And all three paths are Hamiltonian cycles, and all edges are used.
Of course, Claude only proposed the construction method, and a rigorous proof is still needed in mathematics.
Subsequently, Donald Knuth proved that this path indeed visits all m² vertices with the same i value, then covers all i values in turn, and finally forms a complete cycle with a length of m³.
A similar proof also applies to the other two cycles, so the entire problem is solved.
Moreover, Donald Knuth also found through further research that the solution found by Claude is not the only one.
Actually, there are 760 similar decomposition methods, and all these solutions satisfy the same structure. Claude only found one of them.
In addition, Claude only solved the case where m is an odd number.
If m is an even number, there is still no general solution to the problem. In fact, it has been proved that it is impossible for m = 2. So this research is still not completely over.
The greatest significance is not just solving the problem
If there is a truly meaningful aspect to this event, it's not just about solving the problem, but the way AI solves the problem.
In this process, Claude didn't guess the answer but rephrased the problem, wrote programs, and discovered rules. This process is very similar to human research!
For decades, people have generally believed that mathematical proof is the most difficult area for AI to enter.
But this paper shows that AI has started to participate in real mathematical exploration.
In the future, a new research model may emerge - humans propose problems, AI explores the structure, and humans complete the proof.
And this "Claude’s Cycles" may be regarded as a starting point.
Donald Knuth has been writing The Art of Computer Programming for more than half a century. This series of books records the development of human algorithmic thinking.
Now, AI is written into the paper of the godfather of algorithm masters. This may just be the beginning.
Who is Donald Knuth? More than just the godfather of computer science
Donald Knuth, originally named Donald Ervin Knuth, was born on January 10, 1938, in Milwaukee, USA.
Donald Knuth, an American computer scientist and emeritus professor at Stanford University
Donald Knuth is widely recognized as the "godfather" of algorithm analysis and a pioneer in modern computer science. He has made fundamental contributions to several branches