Bilişim ve yapay zekâÖn baskıTeori2 dk okuma

BİLGİSAYAR BİLİMİNDE 1962’DEN KALMA BİR ENGEL YIKILIYOR

Bir Hamilton döngüsü, bir ağın her noktasını tam olarak bir kez ziyaret edip başlangıca dönen bir gidiş-dönüş turudur. Yönlü bir ağda her bağlantı yalnızca tek yönde izlenebilen bir oktur, tıpkı tek yönlü bir sokak gibi. Bu problemin ağırlıklı sürümü, asimetrik gezgin satıcı problemidir.

Böyle bir döngünün var olup olmadığına karar vermek, ders kitaplarına girmiş zor bir problemdir. 1962’de Richard Bellman ve ondan bağımsız olarak Michael Held ile Richard Karp, n noktalı bir ağ için problemi yaklaşık 2ⁿ sürede (yalnızca polinom biçiminde büyüyen çarpanlar dışında) çözen dinamik programlama algoritmaları verdi. Altmış yılı aşkın süre boyunca kimse genel yönlü ağlarda temelden daha iyisini yapamadı.

Yönsüz kuzen çoktan düşmüştü

İki yönlü bağlantılara sahip ağlar için Andreas Björklund, 2014’te 1,657ⁿ sürede çalışan rastgele bir algoritmayla engeli aştı; makaleye göre bu çalışma ona 2016 EATCS–IPEC Nerode Ödülü’nü kazandırdı. Bu, genel yönsüz ağlar için hâlâ bilinen en hızlı yöntem. Yönlü ağlarda ilerleme yalnızca özel durumlarda — iki parçalı ağlar, nokta başına az bağlantısı olan ağlar — ya da kanıtlanmamış bir hipotez, Strassen’in asimptotik rank sanısı altında geldi.

Yeni sınır

Tokyo Üniversitesi’nden Tomohiro Koana ve Tokyo merkezli CyberAgent şirketinden Soh Kumabe, şimdi yönlü problemi şu sürede çözen rastgele bir algoritma veriyor:

O((375/196)ⁿ) = O(1,9133ⁿ)**.

Genel yönlü ağlar için bu, 1962’den beri üstel fonksiyonun tabanındaki ilk iyileşme.

Tek ve çift sayarak

Zorluk inceliklidir. Döngüleri mod 2 saymak — yalnızca sayılarının tek mi çift mi olduğunu bilmek — 2ⁿ’nin altında zaten mümkündü. Ama çift ve sıfır olmayan bir döngü sayısı, tıpatıp sıfıra benzer. Klasik çözüm, bağlantılara rastgele ağırlıklar vererek belirli bir toplam ağırlıkta tek bir çözüm kalmasını sağlamaktır (yalıtım önsavı, isolation lemma); ama hızlı tek-çift sayma yöntemi ağırlıklarla başa çıkamıyordu.

Yazarların tarifi, sade bir dille:

  1. Döngünün bir okunu tahmin et ve onun yerine o okun bir ucundan diğerine her noktadan geçen bir yol ara.
  2. Her oku 1/50 olasılıkla rastgele sil.
  3. Her noktada gelen okların üç grubunu oluştur ve hayatta kalan her oku rastgele, boş olmayan bir grup kümesine kopyala.
  4. Bir tur varsa, en az (49/50)ⁿ⁻¹ olasılıkla, geçerli yolların sayısı tek olacak biçimde nokta başına bir grup seçilebilir.
  5. Her oka değil, her gruba rastgele bir ağırlık ver. Artık yalıtım hilesi çalışıyor ve yaklaşık (50/49)ⁿ tekrar yetiyor.
  6. Her tekrar, Björklund, Kaski ve Koutis’e ait matris determinantı toplamlarını ve Arvind ile Guruswami’nin de kullandığı rastgele bir “doğrusallaştırmayı” kullanarak, her toplam ağırlıktaki tek-çift sayımlarını (15/8)ⁿ sürede hesaplıyor.

İkisini çarpın: (50/49)ⁿ × (15/8)ⁿ = (375/196)ⁿ ≈ 1,9133ⁿ.

Bir makinenin ürettiği kanıt

Makale üretken yapay zekâ hakkında bir beyanla bitiyor: ana teoremin kanıtını ChatGPT 6 Astra üretti ve metnin taslağına yardım etti. Yazarlar, modelin özgün çözümünün kombinatoryal bir okumasını sunan ara önermelerin ifadelerini sağladı, ardından her şeyi doğrulayıp gözden geçirdi ve tüm sorumluluğu üstleniyor.

Sonuç kuramsal — hiçbir program çalıştırılmadı — ve algoritma rastgele; her iki yönde de küçük bir hata olasılığı var. Tek yönlü sokaklar için 1,9133 ile iki yönlüler için 1,657 arasında geniş bir aralık hâlâ açık.