In a new paper, legendary computer scientist Donald Knuth, describes a significant breakthrough in combinatorial mathematics achieved via artificial intelligence (AI). "'AI' greatly surprised me for the first time, (See my unpublication 'Claude's cycles.')," he says.
Knuth describes his "shock" at discovering that Claude Opus 4.6, an Anthropic hybrid reasoning model, solved an open problem regarding directed Hamiltonian cycles that had stymied him for weeks.
The challenge involved a specific graph. Knuth sought a general construction to decompose the arcs of this graph in a specific way. While empirical solutions existed for small graphs, a general formula for all odd values remained elusive until Claude's intervention.
Claude followed a meticulous, step-by-step strategy that spanned thirty-one different attempts to crack the problem. The AI began by looking at the challenge from different angles, trying to find simple mathematical patterns or using brute-force searches. A major turning point occurred when the AI decided to stop looking at the grid as a whole and instead began grouping the points into layers. Even after this breakthrough, Claude faced several "near misses" and experiments that led to dead ends. Eventually Claude had to move away from rigid search methods toward a more creative mathematical "thinking cap". This persistence paid off in its thirty-first attempt, where it finally authored a specialized computer program that successfully mapped out the cycles for every odd-numbered grid size tested.
A dramatic advance in automatic deduction and creative problem solving
Knuth rigorously verified the AI's construction, providing a proof that the discovered rules indeed yield Hamiltonian cycles. He notes that while Claude's solution is one of 760 possible "Claude-like" decompositions, its ability to deduce the correct "thinking cap" for the problem was highly impressive.
This endorsement is a landmark moment in the field. Knuth, a figure synonymous with the rigorous foundations of computer science, is "not an AI hype guy," notes Boing Boing. But now he admits that he may have to revise his "opinions about 'generative AI' one of these days." His celebration of this "dramatic advance in automatic deduction and creative problem solving" signals a major shift in how legendary practitioners view the role of AI in creative problem-solving and formal mathematics.