Donald Knuth to nazwisko, którego nie trzeba przedstawiać osobom, które miały sposobność przejść semestr przedmiotu ASD (Algorytmy i struktury danych) czy liznęły podstawy informatyki teoretycznej. Najpowszechniej znany ze swojej książki "Sztuka programowania" będąca zbiorem algorytmów i struktur danych wraz z dowodami dla podstawowych zagadnień z zakresu informatyki. Ja raczej w pierwszej kolejności kojarzył je będę z algorytmem KMP (Knutha-Morrisa-Pratta) służącym do wyszukiwania wzorca w tekście w zamortyzowanym czasie liniowym, dzięki tabeli prefiksowej.
Profesor opublikował WP-ka, w którym jest pod wrażeniem możliwości ostatnich modeli AI (w tym konkretnym przypadku Claude 4.6) do tego stopnia, że jak stwierdził "musi zrewidować swoje poglądy na temat generatywnej AI".

Przedstawiony problem z zakresu teorii grafów dotyczył podziału grafu skierowanego o pewnych założeniach na 3 cykle Hamiltonowskie spełniające pewne warunki i był następujący:

Rozważ graf skierowany o m³ wierzchołkach oznaczonych jako ijk, gdzie 0 < i, j, k < m. Z każdego wierzchołka wychodzą trzy łuki (krawędzie skierowane) prowadzące odpowiednio do: i⁺jk ij⁺k ijk⁺ gdzie i⁺ = (i + 1) mod m. Spróbuj znaleźć ogólny rozkład łuków na trzy cykle skierowane o długości m³ każdy, dla wszystkich m > 2.

Profesor Knuth znalazł rozwiązania dla m = 3, a jego przyjaciel Filip Stappers metodą "ręczną" dla m od 4 do 16. Nie mogli jednak tego uogólnić do dowolnego m. AI, które zastosowało 31 różnych technik, to się udało.

Oczywiście trzeba brać pod uwagę, że:

• AI dostawało feedback zwrotny od osoby promptującej, która była specjalistą w dziedzinie (zapewne szybko i intuicyjnie mógł wykreślić rzeczy fundamentalnie głupie);
• AI dostało przykłady rozwiązań dla m: 3 ⩽ m ⩽ 16 i na tych pomysłach bazowało;
• Finalny w pełni poprawny formalnie dowód musiał zostać zapisany przez człowieka.

Nadal jak dla mnie daleko do pełnej automatyzacji dowodów nowych rzeczy przez AI (w szczególności tych wymagających wymyślenia kreatywnie rzeczy, które nie istnieją), ale na pewno jako narzędzie wspomagające będzie (już jest) przydatne.