Zaman ve hafıza alanı, neler hesaplayabileceğimiz konusundaki iki ana kısıtlamadır ve ilişkilerini anlamak, hesaplamalı karmaşıklık araştırmasının önemli bir parçasıdır
Zaman ve mekan hesaplama ile nasıl ilişkilidir? Yeni bir cevabımız var
Bir hesaplamanın gerektirdiği bellek miktarı ile ne kadar sürdüğü arasındaki ilişki hakkında şaşırtıcı bir keşif, bilgisayar bilimcilerini büyüledi – ancak herhangi bir pratik uygulama olup olmadığı açık değil.
Massachusetts Teknoloji Enstitüsü’nde Ryan Williams, “Bu benim dünya görüşümü sallıyor” diyor. “Hala var olduğu için şok oldum.”
Zaman ve hafıza alanı, neler hesaplayabileceğimiz konusundaki iki ana kısıtlamadır. Bazı problemler çok fazla bellek, biraz zaman ve birçoğu her ikisini de gerektirir. Bu kısıtlamaları incelemek, bir bilgisayarın belirli bir görev yapmak için atılan adım sayısı ve görevin gerektirdiği bellek yuvası olarak alan olarak adlandırılan hesaplama karmaşıklığı araştırmacılarıdır.
Sezgisel olarak bu değerler bağlantılıdır, çünkü bir görev x adımları gerektiriyorsa, bilgisayarın her adım için belleğine erişmesi gereken en kötü senaryoda, x bellek yuvaları gerektirecektir.
Ancak araştırmacılar, bu en kötü durum senaryosunda gereken bellek miktarı için çıtayı düşürebildiler. 1970’lerde, aslında, X adımlarını atan herhangi bir hesaplamanın X/Log X ile belleğin yapılabileceği keşfedildi. Örneğin 100 zaman adım atan bir program, günlük 100 2’ye eşit olduğu için her zaman 50 bellek yuvası içinde çalışabilir.
Illinois Teknoloji Enstitüsü’nden Lance Fortnow, “Geçen haftaya kadar bildiğimiz en iyi şey bu” diyor. Ancak Williams, bunun dramatik bir şekilde azalabileceğini gösteren şaşırtıcı bir kağıt yayınladı-X Log X’in kare kökü ile 100 veya 50 bellek yuvası yerine, 100 adımlı bir sorun aslında 15 yuvaya indirilebilir.
Fortnow, “Ryan bu makaleyi geçen hafta gönderdiğinde biraz şok oldu ve hepimiz ‘vay’ gibiydik” diyor.
Williams’ın kendisi eşit derecede şaşırdı. “Kendimi sadece yanlış olmadığına ikna etmek aylar aldı” diyor. “Başımı etrafına sarmak benim için hala çok zor. Tüm adımları, kanıtları gözden geçirebilirim ve her adımın doğru olduğunu ve bunun doğru olduğunu doğrulayabilirim. Ama sonunda hala merak ediyorum. ”
Bulgu olası görünmüyor, çünkü bilgisayarların bir sorunun küçük bir kısmını hafızada tutmak için yeterli alana ihtiyacı olduğu anlamına geliyor-biraz insanlar her şeyi yazmaya gerek kalmadan karmaşık, çok aşamalı bir matematik problemini çözebilecek gibi.
Williams’ın yaklaşımı, ağaç değerlendirme problemi olarak bilinen şeye bağlıdır. Bu, ağacın “kökü” ndeki nihai sonucun hesaplanmasının “yaprakları”, sonra “dalları” vb. Ağaç değerlendirme problemini çözmedeki son gelişmeler, bunu zaten dolu olan bilgisayar belleğini yeniden kullanabilen bir algoritma ile yapmanın mümkün olduğunu göstermiştir-kendisi tamamen beklenmedik bir keşif.
Bunu zaman ve mekan meselesine katılmak için Williams, herhangi bir hesaplama problemini temsil edebilecek bir model yarattı, daha sonra yeni ağaç değerlendirme algoritmasını uygulayarak, gereken bellek miktarını büyük ölçüde azaltabileceğini gösterdi. Nihayetinde geçerli cevaplar sağlayan matematiksel hileler ve “büyülü iptaller” içeriyor.
Yeni algoritmayı geliştiren araştırmacılardan Çek Cumhuriyeti’ndeki Charles Üniversitesi’nde Ian Mertz, “Heyecan verici hissediyor” diyor. “Kesinlikle mantıksız bir sonuç, ancak ağaç değerlendirme algoritmalarımızın zaten oldukça mantıksız olduğunu söylese de.”
Ancak keşfin büyüklüğü bilgisayar bilimcilerini şok ederken, bilgisayarları kullanma şeklimizi değiştirmeyecektir. Sorun şu ki, bulgu, bir hesaplama yapmak için gereken bellek miktarını küçültse de, alınan süreyi azaltmayacağını göstermektedir. Bilgisayar belleği oldukça ucuz ve hazır, bu nedenle ihtiyacımız olan miktarı azaltmak bir öncelik değildir.
Tersine izin veren bir keşif, sonuç olarak bilgisayarlara daha fazla bellek ekleyebileceğimiz anlamına gelir – işlemci hızındaki ilerlemeler yavaşlamaya başladığı için çok yararlı olacak bir şey – ancak bunun mümkün olup olmadığı belirsizdir. Mertz, “Artık zaman tasarruflu algoritmaların yerden verimli olabileceğini bildiğimize göre, aynı anda hem zaman hem de mekan için oldukça iyi olan ödünleşmeleri arayabiliriz ve bu gerçek anlamda yararlıdır” diyor Mertz.
Fortnow, çalışma için hemen pratik bir sonuç görmediğini, ancak hesaplama karmaşıklığındaki daha fazla sürprizlerin hala gelebileceği ve zor sorunları nasıl çözdüğümüzü sarsabilecekleri umudunu sağladığını belirtiyor. “Bir kez şok oldun, tekrar şok olabilirsin” diyor.
