Algoritma araştırmalarında yeni bir ufuk: “Biraz bellek, çok zamandan daha güçlü olabilir” teoremi

• MIT'li kuramsal bilgisayar bilimci Ryan Williams'ın yayımladığı yeni ispat, bellek kaynağının zamandan daha güçlü bir hesaplama kaynağı olabileceğini gösteriyor
• Zaman-uzay karmaşıklığı ilişkisine dair 50 yıllık durgunluğu kırarak, tüm algoritmaları daha az bellekle dönüştürmenin bir yolunu sunuyor
• İspatın özü, uzay tasarruflu simülasyonu genelleştirerek, algoritmaların uzay kullanımını zamanın karekökü düzeyine indirme fikri
• Bunun sonucunda, PSPACE ile P sınıfları arasındaki farkı nicel olarak göstermede ilerleme sağlandı ve daha geniş ayrımların ispatına giden yol da açılmış olabilir
• Uzmanlar bu başarıyı “şaşırtıcı bir ilerleme ve yeni bir keşif yolculuğunun başlangıcı” olarak değerlendiriyor; sonucun ileride kuramsal bilgisayar bilimindeki başka zor problemleri çözmek için ipucu olabileceğini düşünüyor

---

One Small Step for Space, One Giant Leap for Complexity

Ryan Williams'ın yeni ispatına genel bakış

• 2024 yazında MIT'den Ryan Williams, kendi ispatını gözden geçirirken hata sandığı fikrin aslında geçerli olduğunu fark etti
• Tüm algoritmaları daha az bellekle çalışabilecek şekilde dönüştüren genel bir prosedür önerdi
• Bunun sonucunda, bazı problemlerin sınırlı zamanla çözülemeyeceği kanıtlanabildi

Zaman ve uzay: hesaplamanın iki kaynağı

• Her algoritma zaman ve bellek (uzay) kullanır
• Daha önce, belirli problemleri çözerken uzayın zamanla orantılı olduğu düşünülüyordu
• Williams'ın ispatı, uzayın zamandan daha güçlü olabileceğini matematiksel olarak ortaya koyuyor

Kuramsal bilgisayar biliminin başlangıcı ve tarihi

• Juris Hartmanis ve Richard Stearns, 1960'larda zaman/uzay karmaşıklığı tanımını oluşturdu
• Problemleri çözmek için gereken kaynaklara göre karmaşıklık sınıfları halinde ayırmanın temelini attılar
• P, makul sürede çözülebilen problemleri; PSPACE ise uygun miktarda bellekle çözülebilen problemleri ifade eder

İlk ilerleme: 1975'teki simülasyon tekniği

• Hopcroft, Paul, Valiant, tüm algoritmaları biraz daha az uzay kullanan biçime dönüştüren evrensel bir simülasyon prosedürü geliştirdi
• Bu, zaman ile uzay arasındaki bağlantıyı anlamada ilk adım oldu, ancak sonrasında bir sınıra takıldı
• Veri aynı anda aynı uzayı paylaşamaz varsayımı nedeniyle daha ileri gitmenin mümkün olmadığı düşünülüyordu

Dönüm noktası: Squishy Pebbles

• 2010'da öncü karmaşıklık kuramcısı Stephen Cook ve çalışma arkadaşları, ağaç değerlendirme problemi - Pebbles and Branching Programs for Tree Evaluation adlı bir görev tasarlayarak, belirli bir eşik altındaki uzay bütçesine sahip algoritmalar için bu görevin imkânsız olduğunu kanıtladı
  • Ancak bir açık vardı. Bu ispat, Paul ve çalışma arkadaşlarının onlarca yıl önce kullandığı aynı sezgisel varsayıma dayanıyordu
  • Yani algoritmalar, zaten dolu olan bir uzaya yeni veri yazamazdı
  • 10 yılı aşkın süre boyunca karmaşıklık kuramcıları bu açığı kapatmaya çalıştı
• Stephen Cook'un oğlu James Cook ile Ian Mertz, 2023'te mevcut varsayımı bozan bir ağaç değerlendirme problemi algoritması yayımladı: Tree Evaluation Is in Space 𝑂 (log 𝑛 · log log 𝑛)
• Bellekteki verinin fiziksel olarak üst üste binebileceği yeni bir temsil modeli önerdiler
• Bu yaklaşım, mevcut simülasyon sınırlarını aşmanın anahtarı oldu

Williams'ın belirleyici sıçraması

• Öğrencilerin sunumu sayesinde Cook-Mertz tekniğiyle tanışan Williams, bunu evrensel simülasyona uygulama fikrini geliştirdi
• Yeni simülasyon, algoritmaların uzay gereksinimini zamanın karekökü düzeyine kadar azaltabiliyor
• Son makalesini 2025 Şubat'ında arXiv'de yayımladı ve akademi dünyasından büyük övgü aldı

Bu sonucun anlamı

• Bu ispat, PSPACE > P olduğunu doğrudan kanıtlamasa da, o yöne doğru ilerleyen bir 'gedik' açan belirleyici bir başarı
• Gelecekte bu prosedür tekrar tekrar uygulanıp daha büyük bir ayrım yaratılabilirse, P vs PSPACE probleminin çözümüne yaklaşmak mümkün olabilir
• Bu, bilgisayar biliminin en eski büyük problemlerinden birini çözmeye giden ilk ipucu olabilir

Etkileyici bir kapanış

• Williams sonuç hakkında şöyle diyor:
  “Aslında gerçekten kanıtlamak istediğim şeyi kanıtlayamadım ama sonunda kanıtladığım şey, istediğimden daha da iyiydi.”

[nunojay]

....Ha?

[GN⁺]

Hacker News görüşleri

• Fuzz ayrıntısını bir kenara bırakırsak, zaman t içinde çalışan çok bantlı bir Turing makinesi O(sqrt(t log t)) alan kullanılarak simüle edilebilir (genelde süre t'den daha uzun olur) Simulating Time With Square-Root Space
  • Quanta yazılarının matematiğe fazla şiirsel ya da abartılı ifadeler katıp yanlış anlamalara yol açması üzücü. Quanta makalesinde “belirli görevler çalıştırma süresiyle orantılı miktarda alan gerektiriyordu” deniyor ama yalnızca karmaşıklık hiyerarşisine bakınca bile böyle genel bir sezgi çıkmıyor. “Bazı algoritmalar” hakkında söylenen bir şeyden genel bir sezgi üretilemez.
  • Okura fazla mı nazik davranıyorlar bilmiyorum ama Quanta'nın P karmaşıklık sınıfını sadece “makul sürede çözülebilen tüm problemler” diye açıklayıp polynomial teriminin kendisini hiç kullanmaması biraz küçümseyici geliyor.
• Perl felsefesini yansıtan “Camel Book”ta şöyle bir ifade var: “Belleğiniz yetmiyorsa satın alabilirsiniz ama zamanınız yetmiyorsa yapabileceğiniz bir şey yoktur.” Sırf eğlenceli bir kitap olduğu için seviyorum.
  • Ama bunun da iki tarafı var. Bilgisayarın belleğinden fazlasına ihtiyaç duyan bir programı hemen çalıştıramazsınız; öte yandan uzun sürse bile bir şeyi en azından çalıştırabilirsiniz, yani zaman da sonuçta önemli bir kaynaktır.
• Önceden hesaplanmış değerleri saklayan lookup table'ların zaferi. Eskiden, tüm hesaplamaları merkezi olarak depolayabilsek işlemciye bile gerek kalmadan işlem hızının devrim yaratabileceğini düşünürdüm (tabii hızlı erişim de başlı başına zor bir problem).
  • Yıllar önce depolama sistemlerinde çalışmaya başladığımda tüm 4KB blokları önceden hesaplayıp saklamayı önermiştim; sonra benzersiz 4KB blok sayısının evrendeki atom sayısından fazla olduğu söylenince çok şaşırmıştım.
  • HashLife adlı algoritma Conway's Game of Life üzerinde buna benzer bir şeyi Turing-tam biçimde yapıyor. Bu kadar karmaşık ve çeşitli durumlarda bile gelecekteki durumları sıçrayarak önceden hesaplayabilmesi bana hep etkileyici gelmiştir.
  • retrieval (arama) lookup işleminin kendisini de cache'leme fikrinde bir sorun yok diye yapılan şaka.
  • Bu aslında topluluk ölçeğinde cache'leme, yani önceden derlenmiş yazılım dağıtımı biçiminde fiilen uygulanıyor. Verimli derleyemediğimiz için dil özelliklerinden vazgeçmek zorunda kalma şeklindeki geleneksel engel, bulutta paralel derleme ve dünya çapında cache ile aşılabilir. Bir sürüm yalnızca bir kez derlense herkes kullanabilir.
  • “Tüm hesaplamaları merkezi olarak depolasak işlemciye gerek kalmazdı” fikrinin devamı olarak, arama geçmişini bile tamamen memoize etmeyi düşünüyorum.
• Quanta'nın şiirsel üslubu yüzünden bu araştırmanın gerçek bilgisayarlara pratikte uygulanıp uygulanamayacağını, yoksa tamamen kuramsal bir senaryo mu olduğunu anlamak zor. Daha fazla bellek kullanmak karşılığında bilgisayarın yavaşlaması mı kastediliyor diye merak ediyorum.
• Uzun süredir raster grafik programlama yapıyorum ve lookup table kullanımı doğal olarak içime işlemiş durumda. Son zamanlarda çeşitli şekilleri önceden DB'ye koyup her sorguda optimize edilmiş sonucu kullanabilen sunucu araçları geliştiriyorum. Karmaşık değil, sezgisel bir desen. Bunu MIT'deki bir profesörden özellikle öğrenmedim; sadece iş yapış tarzımın parçasıydı. Bunun matematiksel olarak da doğrulandığını görmek hoşuma gitti. Pek çok algoritmik bilgi birikiminin aslında sahadaki uygulayıcıların deneyiminden çıkması sık görülen bir durum bence (ör. winding number algoritması).
  • Oyun optimizasyonunda son zamanlarda elde ettiğim kazanımların hepsi, lookup table'ları duruma göre ele alma biçiminden geliyor. Lookup table olmak için mutlaka statik dizi olmaları gerekmiyor; zamanla biraz değişen veriler de aynı şekilde kullanılabiliyor. GPU üzerinde işlem yapma fikrine bu sayede daha çok ısındım ve derleme ya da çalışma anında statik üretilen tabloların yalnızca bir kısmını çalışma sırasında değiştirip texture gibi GPU'ya göndermek oldukça verimli oluyor. Lookup table dediğimiz şeyin sınırı nerede başlıyor, nerede bitiyor bulanıklaşıyor.
• Alanın (belleğin), zamana kıyasla çok daha fazla sayıda sonucu ifade edebildiği sezgisel olarak mantıklı geliyor. Uzunluğu n olan bir bantta O(n) süre boyunca yazabilirsiniz ama bant ikiliyse uzunluğu n olan bir bantta 2^n farklı yapılandırma vardır. Alanı doğru kullanırsanız zamana göre çok daha yüksek ifade gücü elde edersiniz diye düşünüyorum.
  • Benim sezgim şu: tek bir hücre yüzlerce hesaplamanın ara sonucunu saklayabilir. Ara sonuçları saklayamaz ve her seferinde aynı şeyi yeniden hesaplarsanız verim ciddi biçimde düşer. Cache'te %0 isabet oranı çok nadirdir; çoğu durumda alan kullanarak verimlilik artışı sağlanabilir. Tersi yönde ise tek bir zaman adımıyla yüzlerce hücrelik alanı telafi etmek zordur; mevcut hesaplama mimarisinde sonsuz SIMD mümkün değil.
  • O(1) bellek rastgele erişim varsayımı fazla doğal kabul ediliyor ama gerçekte bilgisayar büyüdükçe erişim maliyeti O(n^(1/3)) düzeyine kadar çıkıyor. Bunu veri merkezlerinde doğrudan hissedebiliyorsunuz. Sanırım bu, UMA dışındaki başka bir modeldi.
  • P ≠ PSPACE kanıtlanmadığı için, sezgisel olarak açık görünen şeyleri matematiksel olarak ispatlamak zor bir alan.
  • Bir yandan doğru, ama paralelleştirilmesi zor problemlerde (ör. alternating machine için PTIME=PSPACE) alan o kadar büyük avantaj sağlamayabilir. Makalede t/log t'den sqrt(t log t)'ye sıçrama çığır açıcı olsa da, sonsuz paralelleştirmeyle bile aşılamayan gerçek sınırlar var gibi görünüyor.
  • Pratikte işin niteliğine göre değişiyor. Depolamaya erişim, atama işleminden çok daha yavaşsa yeniden hesaplamak daha hızlı olabilir.
• Zaman-alan arasındaki “ters ilişki”, bir kaynağı kısıtladığınızda diğerinin en iyi değerine mutlaka ulaşamamanız olarak açıklanabilir. Örneğin sıralama algoritmalarında zaman/alan/kararlılık şeklinde üç kısıt olduğunda, kararlılığı da zorunlu kılarsanız zaman ya da alan verimliliği düşer. Bugün hâlâ kararsız sıralamalar kadar hızlı ve az bellek kullanan kararlı bir sıralama yok.
• Kişisel olarak Quanta Magazine'in makale tarzını seviyorum. Yalnızca bilgisayar bilimcilere değil, ilgili alanlara meraklı genel okura da ufuk açıyor. Kuşbakışı çerçevesi ve samimi anlatımı yeni bakış açıları ve fikirler kazandırıyor.
• Ryan Williams'ın konuşma ve makale bağlantılarını paylaşmış.
• Tek bantlı bir Turing makinesi girdi olarak ikilik bir N alıp bandın sağına N tane 1 yazmaya çalışırsa, N zamanda N hücre alan gerektiriyor gibi görünüyor. Ama bunun N'den daha az alanla nasıl simüle edilebildiğini merak ediyorum. Turing makinesinin bantta keyfi bir konuma atlayamayan yapısı nedeniyle, bunun gerçek bilgisayarlarla ilişkisi ne diye de düşünüyorum.
  • Çok bantlı Turing makinesi tek bantlı olana göre çok daha hızlıdır ve burada sözü edilen “alan”, girdi/çıktı hariç geçici çalışma alanıdır.
  • Makale esas olarak karar problemlerini ele alıyor; yani çıktının yalnızca 1 bit olduğu durumları düşünüyor. Çıktı N bitse, bu aslında N adet karar problemini art arda koymakla aynı şey olur.