- Anthropic'in modeli Claude Opus 4.6, Donald Knuth'un birkaç haftadır üzerinde çalıştığı yönlü Hamilton döngüsü ayrıştırma problemini çözdü
- Problem, (m^3) köşeli yönlü bir grafın üç Hamilton döngüsüne ayrıştırılmasını bulmakla ilgili ve Claude bunu tek m (odd m) için tamamen çözdü
- Claude, "fiber ayrıştırması", "3B yılanvari (serpentine) desen", derinlik öncelikli arama (DFS), simüle tavlama gibi çeşitli arama stratejilerini aşamalı olarak yürüttü
- Sonunda Python programı biçiminde genel bir çözüm elde edildi ve Filip Stappers bunu m=3'ten 101'e kadar tek m değerleri için doğrulayarak tam ayrıştırmayı onayladı
- Knuth, bu sonucu otomatik muhakeme ve yaratıcı problem çözmede çığır açıcı bir ilerleme olarak değerlendirirken, çift m durumunun hâlâ çözümsüz olduğunu belirtti
Problemin arka planı ve tanımı
- Araştırma konusu, yönlü Hamilton döngüleri (directed Hamiltonian cycles) ile ilgili ve Knuth'un The Art of Computer Programming eserinin ileride çıkacak bir cildinde yer alması planlanıyor
- Graf, (m^3) adet (ijk) köşesinden oluşuyor ve her köşeden üç kenar çıkıyor: (i+jk), (ij+k), (ijk+)
- Amaç, tüm (m>2) için bu kenarları üç yönlü (m^3)-döngüye ayrıştıran genel bir çözüm bulmak
Claude'un arama süreci
- Claude Opus 4.6, Anthropic'in hibrit muhakeme (hybrid reasoning) modeli; Filip Stappers problemi sundu ve ilerleme sürecini belgelemesini istedi
- İlk aşamada Claude, problemi fonksiyonel grafik ve permütasyon atama problemi olarak yeniden tanımladı; doğrusal ve ikinci dereceden fonksiyonel yaklaşımlar denendi ancak başarısız oldu
- Sonrasında sırasıyla DFS araması, 2B yılanvari desen analizi, 3B Gray kodu tabanlı desenler denendi
- Ardından fiber ayrıştırması yaklaşımı tanıtılarak, (s = (i+j+k) \mod m) temelinde katmanlı yapı analiz edildi ve simüle tavlama (SA) ile kısmi çözümler bulundu
Çözümün keşfi ve doğrulanması
- Aramanın 31. adımında Claude, fiber başına tek koordinat bağımlı kurallar kullanan bir Python programı üretti
- Bu program, m=3,5,7,9,11 için tam üç Hamilton döngüsü oluşturdu
- Filip Stappers bunu m=3~101 arasındaki tüm tek m değerlerinde test ederek tam ayrıştırmayı doğruladı
- Knuth bunu C koduna sadeleştirerek sundu ve her döngünün gerçekten (m^3) uzunluğunda olduğunu matematiksel olarak kanıtladı
Genelleme ve matematiksel analiz
- (m=3) için bazı Hamilton döngülerinin tüm tek m değerlerine genellenebildiği doğrulandı
- (m=3) için 11.502 döngüden 1.012'si (m=5)'e genelleniyor, 996'sı ise (m=7)'ye kadar genelleniyor
- Bu 996 döngü, tüm tek m>1 için genellenebiliyor
- "Claude-benzeri" ayrıştırma, yalnızca i, j, s'nin sınır değerlerine (0 veya m−1) bağlı basit kurallarla tanımlanıyor
- Teorem: Bir "Claude-benzeri" ayrıştırmanın tüm tek m>1 için geçerli olabilmesi için, m=3'teki üç döngünün genellenebilir Hamilton döngüleri olması gerekiyor
- Hesaplama sonuçlarına göre, 760 Claude-benzeri ayrıştırma tüm tek m değerlerinde geçerli
Çift m için çözümsüzlük ve sonuç
- Çift m durumu hâlâ açık (open)
- (m=2) için bunun imkânsız olduğu önceki çalışmalarda kanıtlandı
- Claude, (m=4,6,8) için kısmi çözümler buldu ancak genelleme başarısız oldu
- Claude, çift m arayışı sırasında hata ve anormal davranış gösterdiği için arama durduruldu
- Knuth bunu yapay zeka tabanlı otomatik muhakemede tarihî bir başarı olarak değerlendiriyor ve Claude Shannon'ın adına yakışır bir ilerleme olduğunu söylüyor
Ek: Diğer iki döngünün kuralları
- İkinci döngü (c=1):
- (s=0) ise j artar, (0<s<m−1) ise i artar, (s=m−1) olduğunda i>0 ise k artar, i=0 ise j artar
- Üçüncü döngü (c=2):
- (s=0) iken j<m−1 ise i artar, j=m−1 ise k artar
- (0<s<m−1) iken i<m−1 ise k artar, i=m−1 ise j artar
- (s=m−1) ise i artar
- Her döngü için s=0 durumundaki köşe sırası açıkça veriliyor ve bunun üzerinden tüm döngü yapısı kanıtlanabiliyor
1 yorum
Hacker News görüşleri
RL ölçeklenebilirliğinin uygulanabileceği problem alanlarını düşünmek ilginç
Eskiden insan bilişine dayanmak gerekiyordu, ama artık bu tür örüntüler olasılık dağılımının içine işlenmiş durumda ve herkes erişebiliyor
Yine de bilimin sınırı sürekli genişlerken modelin buna yetişip yetişemeyeceği şüpheli
2030'da Anthropic'in Claude'u güncel tutabilmesi için ya (a) sabit bir modelde sürekli öğrenme ya da (b) sürekli eğitim gerekecek; ikisi de kolay değil
Bilgi cutoff tarihinden sonra sonsuza kadar o anda kalıyorlar
Araştırmacılara ücretsiz çıkarım sunup karşılığında onların düşünce sürecini (trace) eğitim verisi olarak kullanan bir model bile hayal edilebilir
Qwen3-next, Qwen3.5, Nemotron 3 Nano gibi modeller, hibrit attention ile bellek maliyetini düşürerek milyon tokenlık pencereyi destekliyor
İnsan doğrulaması, kod çalıştırma ve arama yoluyla oluşan gerçek zamanlı geri bildirim döngüsü, model için bir öğrenme sinyali işlevi görüyor
Yarısı şaka, ama tamamen imkansız da değil
Eskiden yapılan Wolfram ile Knuth'un GPT-4 sohbetini hatırlattı
Knuth o zamanlar şüpheciydi ama Opus 4.6 gibi son modelleri görünce tavrı biraz yumuşamış gibi
Yeni kanıtlara göre fikrini değiştirebilmek takdire değer
İlgili sohbet burada görülebilir
Bilimsel düşüncenin özü de bu
Knuth'un yazısının giriş kısmı biraz yanlış anlamaya açık gibi geldi
Sanki problemi doğrudan Claude çözmüş gibi görünüyor, ama gerçekte Claude örnekler üretti ve Knuth bunları genelleyip bir ispat haline getirdi
LLM yön belirlemede zayıf ama yön verildiğinde derinlemesine keşif yapmada iyi
Kendi haline bırakıldığında alakasız yerlere gidebiliyor, ama insan yönettiğinde müthiş bir ortak oluyor
Claude problemin özüne nüfuz eden rolü oynadı, insan ise sadece bunu rafine etti
İspatı düzenlemek sadece ikincil bir iş
Claude'un çift durumlarda durması ilginçti
Muhtemelen claude.ai ya da claude code kullanıldı ve sistem context overflow (dumb zone) içine girdi
Copilot'taki gibi bir context kullanım grafiği gösterilip kullanıcının bunu fark etmesi sağlanabilir; faydalı olurdu
Arthur C. Clarke'ın meşhurlaştırdığı pentomino bulmacasını Claude'a çözdürmeyi denedim
Tahtayı ve parçaları 64 bit tamsayılarla temsil eden bir C# programı yazıp hızlıca çözdü, ama 20x3 durumunda hatalı eşleme yüzünden yanlış sonuç verdi
İnsanın yapabileceği türden bir hata olması ilginç
Özetle, Knuth problemi ortaya koydu ve bir arkadaşı Claude ile yaklaşık 30 tur keşif yaptı
Claude tek durumları çözen bir Python programı yazdı, Knuth da bu yaklaşımı ispatladı
Çift durumlar hâlâ çözülmemiş problem olarak duruyor
Gerçekte Claude sık sık duruyor ya da hata veriyordu; insanın yaptığı şey ara sıra hatırlatma yapmaktan ibaretti
Temel fikrin kimden çıktığı ise belirsiz
Bu sıralar çözülmemiş problemlerle uğraşmak gerçekten keyifli bir dönem
10 yıl önceki araştırmaları Claude ile yeniden keşfetmeyi istememe neden oluyor
LLM'lerin gücü üç şeyde yatıyor gibi: muazzam bilgi birikimi, bağlantı kurma yeteneği, yorulmadan deneme-yanılma
Bu üçü birleşince bazen şaşırtıcı sonuçlar çıkıyor
Belki de P≠NP ispatı, insanların göremediği silik bir bağlantıda yatıyordur
LLM bunun içindeki yalnızca bir bileşen
Diğer koşullar eşitse belirleyici fark bu
Tamamen yeni bağlantılar kurmak hâlâ zor
“LLM'ler sadece bir sonraki kelimeyi tahmin eden makineler” sözünün doğru olup olmadığından emin değilim
Öyleyse bu tür problem çözmeyi nasıl açıklayacağız? Bu 'düşünme' mi?
“En yüksek olasılıklı kelime” ifadesi aşırı basitleştirilmiş bir anlatım
Sonuçta “bir sonraki olacak şeyi iyi tahmin edebilme” yeteneğinin kendisi bile zekanın tanımı olabilir
RLHF sayesinde basit tahmin değil, yardımcı cevaplar üretmesi için ödüllendiriliyor
Bu yüzden “delve” gibi ifadeler gereğinden sık ortaya çıkıyor
İlgili içerik için AI SIGNS belgesine bakılabilir
LLM'ler işte bu dağılımı öğreniyor
Bunu indirgemeci biçimde küçümsemek, teknolojinin özünü kaçırmak demek
Bunun bizzat Knuth'un raporu olması ilginç
LLM yardımı olmadan doğrudan okuyup anlama zamanı