YASAK KARŞILAŞTIRMALARLA SIRALAMA, NEREDEYSE O KADAR HIZLI
n öğeyi ikişer ikişer karşılaştırarak sıraya dizmek için yaklaşık n log n karşılaştırma hem gerekli hem de yeterlidir. Ama bu, herhangi iki öğenin karşılaştırılabileceğini varsayar.
Çoğu zaman karşılaştırılamazlar. Yazarlar 2011 tarihli bir makaleden bir örnek ödünç alıyor: aynı işe, her birinin referansları olan birkaç aday başvuruyor. İki aday ancak bir referans ikisini de tanıyorsa karşılaştırılabilir. İzin verilen karşılaştırmalar bir ağ, bir çizge (graph) oluşturur: her öğe bir nokta, izin verilen her karşılaştırma bir bağlantıdır. Gerçek sıra gizlidir, ama çizgenin onu, her öğeyi bir sonrakine bağlayan bir yol olarak içerdiği garantidir. Soru şu: sırayı geri bulmak için kaç karşılaştırma gerekir? Buna genelleştirilmiş sıralama (generalized sorting) denir.
Olağan hileler neden işe yaramıyor
Klasik algoritmalar seçme özgürlüğüne dayanır. QuickSort bir “pivot” seçer ve onu diğer öğelerin çoğuyla karşılaştırır, ama keyfi bir çizgede diğerlerinin çoğuna bağlı hiçbir öğe olmayabilir. MergeSort öğeleri gruplara ayırır ve her birini sıralar, ama bir grup kendi başına sıralanamayabilir: nihai sırada komşu olan iki öğenin grubun içinde birbirine bağlı olması gerekmez. Daha temelde, sıradan sıralamada olası sıraların önemli bir bölümünü eleyen bir karşılaştırma her zaman vardır; kısıtlı karşılaştırmalarda hiç olmayabilir.
İlerleme yavaş oldu. 2011’de Zhiyi Huang, Sampath Kannan ve Sanjeev Khanna, logaritmik çarpanlar dışında yaklaşık n¹·⁵ karşılaştırma kullanan bir yöntem buldu ve bu sınır o zamandan beri keyfi çizgeler için aşılamadı. Hatta problemin sıradan sıralamadan temelde daha zor olup olmadığını, yani n’nin 1’den büyük bir kuvvetini gerektirip gerektirmediğini sordular.
Önce tahmin et, sonra onar
New York Üniversitesi’nden Sanjeev Khanna, Harvard Üniversitesi’nden Aaron Putterman ve yine New York Üniversitesi’nden Junkai Song şimdi bu soruyu yanıtlıyor: hayır. Rastgeleleştirilmiş algoritmaları, herhangi bir çizgede ortalama yaklaşık n log⁴ n karşılaştırmayla sıralıyor — sıradan sıralamanın yalnızca birkaç logaritmik çarpan üzerinde. Üstelik, yazdıklarına göre, “görece basit”. Ancak kazanç kuramsal: kanıttaki sabitler çok büyük (2³² gibi çarpanlar), bu yüzden avantaj ancak çok büyük n değerlerinde ortaya çıkıyor.
Algoritma bilinen bir sonuca dayanıyor: biri size her bağlantının yönüne dair, w tanesinde yanlış olan bir tahmin verirse, sıra yaklaşık n log n + w karşılaştırmayla geri bulunabilir. Böylece görev, az karşılaştırmayla az hatalı bir tahmin üretmeye dönüşüyor. Temel adımlar:
- Kaba bir ilk tahmin. Bağlı çiftlerden rastgele bir örneklemi karşılaştır ve yanıtlarla tutarlı herhangi bir sıra seç. Bu tahmin çok hata yapar, ama aşırı çok değil.
- Hataları düzeltmek yerine yalıtmak. Algoritma yanlış tahminleri düzeltmek yerine, çizgenin hataların ortalamadan daha yoğun olduğu kısımlarını bulur ve onları bir kenara ayırır. Her tur kalan hataları, beklenen değer olarak, dört kat azaltır.
- Sonra geri dönmek. Bir kenara ayrılan bağlantılar daha sonraki bir aşamada ele alınır. Her aşama hâlâ bekleyen bağlantıların en az yarısını çözer; bu yüzden bir milyon bağlantı için yaklaşık yirmi aşama yeterlidir.
Makinelerle bulunan bir kanıt
Makalenin yapay zekâ beyanı alışılmadık derecede ayrıntılı. Beyan, ChatGPT 6-Astra’nın “geliştirilmiş sınırların kanıtlanmasında vazgeçilmez” olduğunu belirtiyor. Bir model önce yaklaşık n¹·³³ karşılaştırma kullanan bir algoritma buldu, sonra tıkandı. Yazarlar onu n¹·²’ye taşıdı; ardından, birkaç hafta boyunca onlarca kez yönlendirilen modeller art arda iyileştirmeler buldu — n^(10/9), n^(17/16), n^(19/18) — ve sonunda neredeyse doğrusal algoritmaya ulaştı. Yazarlar, kendi ara adımlarının bu son keşif için vazgeçilmez olup olmadığının belirsiz olduğunu da ekliyor.
Hâlâ açık olanlar
Sonuç hesaplama süresini değil, karşılaştırmaları sayıyor: algoritma, ifade edildiği hâliyle, polinom zamanda çalışmıyor; 2011 yöntemi ise çalışıyordu. Yazarlar üç açık soru sıralıyor: kalan logaritmik çarpanların kaldırılıp kaldırılamayacağı, rastgelelik kullanmayan bir algoritmanın aynı başarıyı gösterip gösteremeyeceği ve verimli bir algoritmanın aynı karşılaştırma sayısına ulaşıp ulaşamayacağı — hatta n¹·⁵’i hiç aşıp aşamayacağı.
