Donald Knuth memublikasikan makalah tentang bagaimana Claude Opus 4.6 memecahkan masalah kombinatorika terbuka

Ringkasan inti

• Donald Knuth, ilmuwan komputer penulis 'The Art of Computer Programming (TAOCP)', mengumumkan bahwa model AI terbaru 'Claude Opus 4.6' berhasil memecahkan masalah kombinatorika terbuka yang telah ia teliti selama beberapa minggu.
• Pada masalah menemukan dekomposisi siklus Hamiltonian pada graf berarah, Claude menemukan struktur algoritme tergeneralisasi yang bekerja melalui 31 kali eksekusi skrip Python dan loop umpan balik mandiri.
• Knuth, yang sebelumnya skeptis sambil menyoroti keterbatasan AI generatif, menilai hasil ini sebagai "kemajuan dramatis dalam deduksi otomatis dan pemecahan masalah kreatif" dan mengisyaratkan bahwa ia akan merevisi pandangannya yang lama tentang AI.

Analisis mendalam

Masalah yang dipecahkan: dekomposisi siklus Hamiltonian (Hamiltonian Cycle Decomposition)
Knuth sedang meneliti masalah dekomposisi pada graf berarah tertentu saat menulis volume berikutnya dari TAOCP. Pada graf dengan $m^3$ simpul $ijk$, untuk simpul $0 \le i, j, k < m$, setiap simpul memiliki 3 busur (arcs) yang menuju ke $i+jk$, $ij+k$, dan $ijk+$ (dengan $i+ = (i+1) \bmod m$). Tujuannya adalah menemukan solusi umum (general decomposition) yang mendekomposisikan busur-busur ini menjadi 3 buah siklus berarah sepanjang $m^3$ untuk semua kasus dengan $m > 2$. Knuth telah menyelesaikan kasus $m=3$, tetapi mengalami kesulitan dalam menurunkan rumus generalisasi untuk nilai yang lebih besar.

Prinsip implementasi dan latar belakang teknis: penalaran hibrida dan loop eksplorasi otonom
Rekan Knuth, Filip Stappers, memasukkan masalah ini ke 'Claude Opus 4.6', model penalaran hibrida terbaru dari Anthropic. Di sini, lebih dari sekadar pertanyaan sederhana, prompt diberi batasan kuat yang memaksa workflow agentic.

Claude segera mendefinisikan ulang masalah secara matematis dan menulis skrip Python (exploreXX.py) untuk memulai loop verifikasi hipotesis. Selama sekitar 1 jam, ia mencoba beragam algoritme seperti brute force, fiber decompositions, dan Simulated Annealing, serta melakukan 31 kali eksplorasi.

Titik belok kunci dalam pemecahan masalah
Khususnya pada eksplorasi ke-25, Claude menganalisis keterbatasannya sendiri dengan menyatakan bahwa "algoritme Simulated Annealing dapat menemukan solusi individual, tetapi tidak dapat memberikan konstruksi matematis umum (general construction), sehingga dibutuhkan pendekatan matematika murni," lalu mengubah arah eksplorasinya. Akhirnya, pada eksplorasi ke-31, berdasarkan pola struktural dari eksplorasi sebelumnya, ia berhasil menurunkan konstruksi generalisasi yang tepat dan bekerja saat $m$ ganjil. Berdasarkan hasil ini, Knuth menyelesaikan pembuktian matematisnya dan menamainya 'Claude-like decompositions'.

Kode dan data utama

Berikut sebagian dari batasan inti (prompt) yang diberikan Filip Stappers kepada Claude, serta log evaluasi mandiri yang dicatat Claude.

# 1. Batasan workflow yang diberikan kepada Claude (kontrol loop dan kewajiban dokumentasi)  
"""  
After EVERY exploreXX.py run, IMMEDIATELY update this file [plan.md] before doing anything else.   
No exceptions. Do not start the next exploration until the previous one is documented here.  
"""  
  
# 2. Redefinisi masalah matematis oleh Claude (pendekatan awal)  
"""  
Need sigma: Z3 m — S3, assigning a permutation of {0,1,2} at each vertex;   
cycle c at vertex v goes in direction sigma(v)[c].   
Each resulting functional digraph must be a single Hamiltonian cycle.  
"""  
  
# 3. Evaluasi mandiri Claude setelah eksplorasi ke-25 (perubahan arah)  
"""  
SA(Simulated Annealing) can find solutions but cannot give a general construction.   
Need pure math.  
"""

[bus710]

Orang yang ada di buku teks itu terus nambahin isi ke buku teks....

[skshin]

(Diakui)

[dkang]

Ya, memang menulis buku teks itu peran beliau (angguk).

[onestone]

Wkwkwkwk sekarang sepertinya beliau bakal menambahkan lebih banyak lagi dengan AI ya

[roxie]

Ternyata TAOCP masih akan terus terbit

[kh0324]

Membagikan apa adanya cara menggunakan AI untuk menyelesaikan soal matematika, lalu menulis makalah dengan TeX buatannya sendiri.... super keren

[dolsangodkimchi]

Berkat artikelnya, saya jadi pertama kali tahu tentang TAOCP dan rasanya saya harus mencoba membacanya pelan-pelan.

[jongyeol]

Beliau masih hidup?

[carnoxen]

Bahkan sekarang pun masih mengoreksi...