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

KLİK BULMANIN HIZ SINIRI 40 YIL SONRA YIKILIYOR

n kişilik bir sosyal ağ düşünün. İçlerinde hepsi birbirini tanıyan k kişilik bir grup var mı? Bilgisayar bilimciler böyle bir gruba k-klik (k-clique) der ve bir tane bulmak, sayısız uygulaması olan klasik bir problemdir. Naif yaklaşım, k kişilik her olası grubu, yani kabaca n^k tanesini denetler — büyük ağlar için umutsuz.

1985’ten bir hile ve uzun bir meydan okuma

40 yılı aşkın süre önce Jaroslav Nešetřil ve Svatopluk Poljak bir kestirme buldu. Bir k-klik aramasını daha büyük bir çizgede bir üçgen aramasına dönüştürdüler; bu da kendi payına, büyük sayı tabloları olan matrislerin çarpılmasıyla yapılabilir. Maliyet, matris çarpımının üssü olan ω’ya bağlıdır: Yöntemleri yaklaşık n^(ωk/3) adım sürer. ω’yı kimse tam olarak bilmiyor. En az 2’dir ve makale yakın tarihli bir üst sınır olarak 9/4’ü aktarıyor.

O 1985 yönteminin üssü hiç geçilemedi. 2004’te Gerhard Woeginger, araştırmacılara bazı sabit k değerleri için daha iyisini yapmaları çağrısında bulundu; yirmi yılı aşkın süre geçti. Bu arada, n^(ωk/3)’ün esasen mümkün olan en iyi değer olduğunu söyleyen k-Klik Hipotezi, “ince taneli karmaşıklığın” (fine-grained complexity) temellerinden biri hâline geldi. Araştırmacılar onu, dilbilgilerinin ayrıştırılmasından sıkıştırılmış verilerin analizine kadar başka pek çok problemin de daha hızlı çözülemeyeceğini savunmak için kullandı.

Hareketli bir hedef

Bu hipotezi çürütmenin özel bir zorluğu vardı. Öngördüğü maliyet, bilinmeyen ω’ya bağlı. Bugünkü en iyi ω değerini geçen bir algoritma, biri daha sonra daha hızlı bir matris çarpımı bulursa hipotezi geçmeyi bırakabilir.

MIT’den Virginia Vassilevska Williams ve Tel Aviv Üniversitesi’nden Or Zamir sorunu atlatıyor. Yeterince büyük her k için bir k-kliğin yaklaşık n^((ω/3 − c)k) adımda bulunabileceğini — hatta sayılabileceğini — kanıtlıyorlar; burada c, ne k’ya ne de ω’ya bağlı olan pozitif bir sabit. Tasarruf, ω’nın gerçek değerine göre ölçülüyor; bu değer ne çıkarsa çıksın. Akla gelebilecek en iyi durum olan ω = 2’de bile geçerliliğini koruyor.

Bir kamayı katlamak

Yöntemin kalbi dokuz köşeli örüntülerle ilgili. Standart yaklaşım bunları üçerli üç gruba ayırır ve üç dev matrisi çarpar. Yazarlar bir kamaya (wedge) — bir köşeyi paylaşan iki kenara — bakıyor ve matrislerden ikisinin arasına hiçbir şeyi değiştirmeyen bir tablo yerleştiriyor: birim matris. Ardından bu birim matrisi, her biri kamanın iki kenarını tek bir kenarda birleştiren birkaç “takas”ın toplamı artı düşük ranklı bir artık olarak yazıyorlar.

Takaslar, aynı yöntemle yeniden ele alınan, daha az kenarlı daha basit örüntüler veriyor; dokuz köşeli bir örüntünün en fazla 36 kenarı olduğundan özyineleme sona eriyor. Düşük ranklı artık ise çarpılacak matrisleri küçültüyor. ω = 2 olduğunda bile bir kazancı koruyan şey, hileyi aynı anda iki ayrı kamaya uygulamak. Dokuzun katı olan herhangi bir k, bu durumda dokuz blokta gruplanabilir.

Gerçek ama minicik

Yazarlar kazanç için sayı vermiyor. Sabitlerin “optimizasyon olmadan zerre kadar ile ciddi optimizasyonlarla minicik arasında” değiştiğini söylüyorlar. Mesele pratikteki hız değil: Onlarca yıldır inanılan bir engelin var olmaması.

Sonuçlar kliklerin ötesine uzanıyor. n değişkenli problemlerde yaklaşık 2^(ωn/3) adımda çalışan, Max-Cut ve Max-2-SAT gibi zor optimizasyon problemlerine yönelik kesin algoritmalar da artık daha küçük bir üs elde ediyor. Herhangi bir sabit küçük çizgenin kopyalarını saymak da öyle.

Yapay zekânın yaptığı

Ayrı bir bölümde yazarlar, herkese açık web arayüzü üzerinden kullandıkları ChatGPT-6 ile nasıl çalıştıklarını anlatıyor. Beş kişilik klikler için kendi fikirlerinden ve başka bir varsayımı, Üstel Zaman Hipotezi’ni (Exponential Time Hypothesis) çürüten yakın tarihli bir OpenAI sonucundan yola çıkan model, 5-klikler için ilk, karmaşık bir iyileştirme buldu. Yazarlar ardından bunu, yapay zekânın yardımıyla, ispatın özündeki cebirsel ayrışıma damıttı; bu ayrışımı “neredeyse tamamen yapay zekânın katkısı” olarak görüyorlar. Etrafına kurulan algoritmik çerçeve ise, söylediklerine göre, esas olarak onların.

Bir gözlem öne çıkıyor. Yazarlar, yapay zekânın ürettiği girift ispatları insanların okumasının zor olduğunu belirtiyor — ve “bunların yapay zekânın kendisi için de anlaşılmasının zor olmasından etkilendiklerini” ekliyor.