Algoritmalar İçin Bellek, Zamandan Çok Daha Güçlü Bir Kaynaktır

Bu hikayenin orijinal versiyonu Quanta Dergisi'nde yayınlanmıştır .

2024 yılının Temmuz ayında bir öğleden sonra, Ryan Williams yanıldığını kanıtlamak için yola çıktı. Bilgisayar bilimlerinde zaman ve bellek arasındaki ilişki hakkında çarpıcı bir keşfe imza atmasının üzerinden iki ay geçmişti. Bu, belleğin bilgisayar bilimcilerinin sandığından daha güçlü olduğuna dair matematiksel bir kanıtın kabataslak bir taslağıydı: Küçük bir miktar, akla gelebilecek tüm hesaplamalarda çok fazla zaman kadar faydalı olurdu. Bu o kadar imkansız görünüyordu ki, bir şeylerin yanlış olduğunu varsaydı ve daha az çılgın fikirlere odaklanmak için kanıtı hemen bir kenara bıraktı. Artık sonunda hatayı bulmak için zaman yaratmıştı.

Öyle olmadı. Williams, argümanını saatlerce inceledikten sonra tek bir kusur bile bulamadı.

Massachusetts Teknoloji Enstitüsü'nde teorik bilgisayar bilimcisi olan Williams, "Aklımı kaçırdığımı sandım," dedi. İlk kez, hafızanın, belki de, sadece belki, çalışmalarının öne sürdüğü kadar güçlü olabileceği ihtimalini düşünmeye başladı.

Sonraki aylarda ayrıntıları detaylandırdı, her adımı dikkatle inceledi ve bir avuç araştırmacıdan geri bildirim istedi. Şubat ayında, kanıtını nihayet internette yayınladı ve büyük beğeni topladı.

"Muhteşem. Çok güzel," dedi New Jersey, Princeton'daki İleri Araştırmalar Enstitüsü'nde teorik bilgisayar bilimcisi olan Avi Wigderson . Haberi duyar duymaz Wigderson, Williams'a bir tebrik e-postası gönderdi. Konu satırı: "Aklımı başımdan aldın."

Zaman ve bellek (alan olarak da bilinir), hesaplamanın en temel iki kaynağıdır: Her algoritmanın çalışması biraz zaman alır ve çalışırken veri depolamak için biraz alana ihtiyaç duyar. Şimdiye kadar, belirli görevleri yerine getirmek için bilinen tek algoritmalar, çalışma süreleriyle kabaca orantılı bir alan gerektiriyordu ve araştırmacılar uzun zamandır daha iyisini yapmanın bir yolu olmadığını varsayıyordu. Williams'ın kanıtı, ne yaparsa yapsın, herhangi bir algoritmayı çok daha az alan kullanan bir forma dönüştürmek için matematiksel bir prosedür ortaya koydu.

Dahası, bu sonuç -belirli bir alan içinde neleri hesaplayabileceğinizle ilgili bir ifade- aynı zamanda belirli bir sürede neleri hesaplayamayacağınızla ilgili ikinci bir sonucu da ima ediyor. Bu ikinci sonuç kendi başına şaşırtıcı değil: Araştırmacılar bunun doğru olmasını bekliyorlardı, ancak nasıl kanıtlayacaklarını bilmiyorlardı. Williams'ın kapsamlı ilk sonucuna dayanan çözümü, neredeyse çizgi filmvari bir aşırılık gibi geliyor; gezegendeki herkes için kesin bir mazeret oluşturarak şüpheli bir katili suçlu çıkarmaya benziyor. Aynı zamanda bilgisayar bilimindeki en eski çözümsüz sorunlardan birine saldırmanın yeni bir yolunu da sunabilir.

Washington Üniversitesi'nde bilgisayar bilimcisi olan Paul Beame , "Bu oldukça çarpıcı bir sonuç ve büyük bir ilerleme," dedi. "Bunu Ryan'ın yapması biraz daha az şaşırtıcı."

46 yaşındaki Williams, açık ve ifadeli bir yüze ve hafif gri saçlara sahip. MIT Stata Merkezi'nin renkli kulelerine bakan ofisi, mekanın yaratıcı kullanımının bir başka örneği. Bir çift yoga matı, bir pencere pervazını geçici bir okuma köşesine dönüştürmüş ve masa, matematiksel karalamalarla dolu büyük bir beyaz tahtanın karşısındaki kanepeye yer açacak şekilde tuhaf şekilli bir köşeye yerleştirilmiş.

MIT, Williams'ın Alabama kırsalındaki çocukluk evinden çok uzaktaydı; orada alan sıkıntısı yoktu. 20 hektarlık bir çiftlikte büyüyen Williams, ilk kez 7 yaşındayken annesi onu özel bir akademik zenginleştirme dersi için arabayla ilçenin öbür ucuna götürdüğünde bir bilgisayarla karşılaşmıştı. Dijital havai fişek gösterisi hazırlayan basit bir program karşısında büyülendiğini hatırlıyordu.

Williams, "Rastgele bir renk alıp monitörün ortasından rastgele bir yöne gönderiyordu," dedi. "Hangi görüntüyü elde edeceğinizi tahmin edemezdiniz." Bilgisayar dünyası, sonsuz olasılıklarla dolu, çılgın ve harika bir oyun alanı gibi görünüyordu. Genç Williams buna kapılmıştı.

"Geleceğin bilgisayarında çalıştırılmak üzere kendime kağıda programlar yazıyordum," dedi. "Ailem benimle ne yapacaklarını pek bilmiyordu."

Williams büyüdükçe hayali bilgisayarlardan gerçek bilgisayarlara geçti. Lise son iki yılında, bilgisayar biliminin teorik yönüyle ilk kez karşılaştığı prestijli bir devlet yatılı okulu olan Alabama Matematik ve Fen Okulu'na geçti.

"Dışarıda daha geniş bir dünya olduğunu ve bilgisayarlar hakkında matematiksel düşünmenin bir yolu olduğunu fark ettim," dedi. "Yapmak istediğim şey buydu."

Williams, özellikle teorik bilgisayar biliminin hesaplamalı karmaşıklık teorisi adı verilen bir dalına ilgi duyuyordu. Bu teori, listeleri sıralama veya sayıları çarpanlarına ayırma gibi hesaplamalı problemleri çözmek için gereken kaynaklarla (zaman ve alan gibi) ilgilenir. Çoğu problem, her biri kendine özgü zaman ve alan gereksinimlerine sahip birçok farklı algoritma ile çözülebilir. Karmaşıklık teorisyenleri, problemleri, onları çözmek için en iyi algoritmaların kaynak gereksinimlerine (yani en hızlı çalışan veya en az alan kullanan algoritmalar) göre karmaşıklık sınıfları adı verilen kategorilere ayırırlar.

Peki, hesaplamalı kaynakların incelenmesini matematiksel olarak nasıl titiz hale getirirsiniz? Zaman ve mekanı dakikalarla megabaytları karşılaştırarak analiz etmeye çalışırsanız, çok da ileri gidemezsiniz. Herhangi bir ilerleme kaydetmek için doğru tanımlarla başlamanız gerekir.

Bu tanımlar, sınırlı kaynaklarla idare etme konusunda deneyimli, öncü bir bilgisayar bilimcisi olan Juris Hartmanis'in çalışmalarından ortaya çıkmıştır. 1928'de Letonya'nın önde gelen bir ailesinde doğdu, ancak çocukluğu II. Dünya Savaşı'nın patlak vermesiyle altüst oldu. İşgalci Sovyet güçleri babasını tutuklayıp idam etti ve savaştan sonra Hartmanis liseyi bir mülteci kampında bitirdi. Ders kitaplarını karşılayamamasına rağmen üniversiteye gitti ve orada başarılı oldu.

2009 tarihli bir röportajında , "Derslerde çok detaylı notlar alarak kendimi telafi ettim," diye hatırladı. "Doğaçlama yapıp zorlukların üstesinden gelmenin belli bir avantajı var." Hartmanis, 1949'da Amerika Birleşik Devletleri'ne göç etti ve Kansas City Üniversitesi'nde matematik okurken tarım makineleri üretmek, çelik üretmek ve hatta uşaklık yapmak gibi çeşitli geçici işlerde çalıştı. Teorik bilgisayar biliminin yeni alanında olağanüstü başarılı bir kariyere sahip oldu.

Hartmanis, 1960 yılında New York, Schenectady'deki General Electric araştırma laboratuvarında çalışırken, yaz stajı yapan bir lisansüstü öğrencisi olan Richard Stearns ile tanıştı. Çığır açan iki makalede , zaman ve uzay için kesin matematiksel tanımlar oluşturdular. Bu tanımlar, araştırmacılara iki kaynağı karşılaştırmak ve problemleri karmaşıklık sınıflarına ayırmak için ihtiyaç duydukları dili sağladı.

En önemli sınıflardan biri mütevazı bir isimle "P" olarak bilinir. Kabaca söylemek gerekirse, makul bir sürede çözülebilecek tüm problemleri kapsar. Uzay için benzer bir karmaşıklık sınıfına "PSPACE" adı verilir.

Bu iki sınıf arasındaki ilişki, karmaşıklık teorisinin temel sorularından biridir. P'deki her problem aynı zamanda PSPACE'dedir, çünkü hızlı algoritmaların bilgisayar belleğindeki fazla alanı dolduracak kadar zamanı yoktur. Tersi ifade de doğru olsaydı, iki sınıf eşdeğer olurdu: Uzay ve zaman karşılaştırılabilir hesaplama gücüne sahip olurdu. Ancak karmaşıklık teorisyenleri, PSPACE'in çok daha büyük bir sınıf olduğundan ve P'de olmayan birçok problem içerdiğinden şüpheleniyorlar. Başka bir deyişle, uzayın zamandan çok daha güçlü bir hesaplama kaynağı olduğuna inanıyorlar. Bu inanç, algoritmaların aynı küçük bellek parçasını tekrar tekrar kullanabilmesinden, zamanın ise o kadar affedici olmamasından kaynaklanıyor; bir kez geçtiğinde onu geri alamazsınız.

Williams, "Sezgi çok basit," dedi. "Mekânı yeniden kullanabilirsiniz, ama zamanı yeniden kullanamazsınız."

Ancak sezgi, karmaşıklık teorisyenleri için yeterli değil: Kesin kanıtlar istiyorlar. PSPACE'in P'den büyük olduğunu kanıtlamak için araştırmacıların, PSPACE'deki bazı problemler için hızlı algoritmaların kesinlikle imkansız olduğunu göstermeleri gerekecek. Peki nereden başlayacaklar?

Tesadüfen, Hartmanis'in 1965'te yeni kurulan bilgisayar bilimleri bölümünün başına geçmek üzere taşındığı Cornell Üniversitesi'nde işe başladılar. Onun liderliğinde bölüm hızla karmaşıklık teorisi üzerine bir araştırma merkezi haline geldi ve 1970'lerin başında, oradaki iki araştırmacı, John Hopcroft ve Wolfgang Paul, zaman ve mekan arasında kesin bir bağlantı kurmaya koyuldular.

Hopcroft ve Paul, P ve PSPACE problemini çözmek için belirli hesaplamaların sınırlı bir sürede yapılamayacağını kanıtlamaları gerektiğini biliyorlardı. Ancak olumsuz bir sonucu kanıtlamak zordur. Bunun yerine, problemi tersine çevirip sınırlı bir alanda neler yapılabileceğini araştırmaya karar verdiler. Belirli bir alan bütçesi verilen algoritmaların, biraz daha büyük bir zaman bütçesine sahip algoritmalarla aynı problemleri çözebileceğini kanıtlamayı umuyorlardı. Bu, alanın zamandan en azından biraz daha güçlü olduğunu gösterirdi; PSPACE'in P'den daha büyük olduğunu gösterme yolunda küçük ama gerekli bir adım.

Bu amaçla, karmaşıklık teorisyenlerinin simülasyon adını verdiği, mevcut algoritmaları aynı problemleri farklı alan ve zaman miktarlarıyla çözen yeni algoritmalara dönüştürmeyi içeren bir yönteme yöneldiler. Temel fikri anlamak için, kitaplığınızı alfabetik sıraya koymak için hızlı bir algoritma verildiğini, ancak kitaplarınızı düzinelerce küçük yığın halinde dizmeniz gerektiğini düşünün. Daha uzun sürse bile, dairenizde daha az yer kaplayan bir yaklaşımı tercih edebilirsiniz. Simülasyon, daha uygun bir algoritma elde etmek için kullanabileceğiniz matematiksel bir işlemdir: Orijinal algoritmayı yükleyin, size zamandan tasarruf sağlayan yeni bir algoritma verecektir.

Algoritma tasarımcıları, sıralama gibi belirli görevler için bu uzay-zaman dengelerini uzun zamandır inceliyorlar. Ancak zaman ve uzay arasında genel bir ilişki kurmak için Hopcroft ve Paul daha kapsamlı bir şeye ihtiyaç duyuyorlardı: Çözdüğü problem ne olursa olsun her algoritma için işe yarayan, yerden tasarruf sağlayan bir simülasyon prosedürü. Bu genellemenin bir bedeli olacağını düşünüyorlardı. Evrensel bir simülasyon, belirli bir problemin ayrıntılarını kullanamayacağı için, muhtemelen özel bir simülasyon kadar yer tasarrufu sağlamayacaktır. Ancak Hopcroft ve Paul çalışmalarına başladıklarında, yerden tasarruf etmek için bilinen evrensel yöntemler yoktu. Küçük bir miktar tasarruf bile ilerleme sayılırdı.

Atılım, Hopcroft ve Paul'un Leslie Valiant adlı genç bir araştırmacıyla iş birliği yapmasıyla 1975 yılında gerçekleşti. Üçlü, her zaman biraz yerden tasarruf sağlayan evrensel bir simülasyon prosedürü geliştirdi. Hangi algoritmayı kullanırsanız kullanın, alan bütçesi orijinal algoritmanın zaman bütçesinden biraz daha küçük olan eşdeğer bir algoritma elde edersiniz.

Valiant, "Bu kadar uzun sürede yapabileceğiniz her şeyi, biraz daha az alanda da yapabilirsiniz," dedi. Bu, uzay ve zamanı birbirine bağlama arayışının ilk büyük adımıydı.

Ancak daha sonra ilerleme durdu ve karmaşıklık teorisyenleri temel bir engele çarptıklarından şüphelenmeye başladılar. Sorun tam da Hopcroft, Paul ve Valiant'ın simülasyonunun evrensel karakteriydi. Birçok problem zamandan çok daha az alanla çözülebilse de, sezgisel olarak bazıları neredeyse zaman kadar alana ihtiyaç duyacak gibi görünüyordu. Eğer öyleyse, daha fazla alan tasarrufu sağlayan evrensel simülasyonlar imkansız olurdu. Paul ve diğer iki araştırmacı, görünüşte bariz bir varsayımda bulunulması koşuluyla, bunların gerçekten imkansız olduğunu kısa sürede kanıtladılar: Farklı veri yığınları aynı anda bellekte aynı alanı kaplayamaz.

Wigderson, "Herkes daha iyisini yapamayacağınızı varsayıyordu" dedi.

Paul'ün sonucu, P ve PSPACE problemini çözmenin, simülasyonu tamamen bırakıp farklı bir yaklaşım benimsemeyi gerektireceğini gösteriyordu, ancak kimsenin iyi bir fikri yoktu. Sorun 50 yıl boyunca böyle devam etti; ta ki Williams sonunda tıkanıklığı çözene kadar.

Öncelikle üniversiteyi bitirmesi gerekiyordu.

1996'da Williams'ın üniversitelere başvurma zamanı gelmişti. Karmaşıklık teorisi alanında eğitim almanın onu evinden çok uzağa götüreceğini biliyordu, ancak ailesi Batı Yakası ve Kanada'nın söz konusu olamayacağını açıkça belirtmişti. Geriye kalan seçenekleri arasında, en sevdiği disiplinin tarihindeki önemli yeri nedeniyle Cornell öne çıkıyordu.

"Bu Hartmanis denen adam zaman ve mekan karmaşıklığı derslerini tanımladı," diye düşündüğünü hatırladı. "Bu benim için önemliydi."

Williams, cömert bir maddi yardımla Cornell'e kabul edildi ve 1997 sonbaharında, kendisi de bir karmaşıklık teorisyeni olmak için elinden gelen her şeyi yapmayı planlayarak geldi. Tek fikirliliği, diğer öğrencilerin dikkatini çekti.

Cornell'de Williams ile aynı dönemde çalışan Teksas Üniversitesi Austin'deki bilgisayar bilimcisi Scott Aaronson , "Karmaşıklık teorisine çok meraklıydı" dedi.

Ancak ikinci sınıfta Williams, sezgiden ziyade matematiksel kesinliğe vurgu yapan derslerde ayak uydurmakta zorlanıyordu. Hesaplama teorisi dersinden orta not aldıktan sonra, öğretmeni ona başka kariyerler düşünmesini önerdi. Ancak Williams hayalinden vazgeçmedi. Daha zor olan dersten aldığı mükemmel notun lisansüstü başvurularında etkileyici görüneceğini umarak, bir lisansüstü teori dersine kaydoldu. Bu lisansüstü dersi veren profesör, o zamanlar alanında kıdemli bir devlet adamı olan Hartmanis'ti.

Williams, Hartmanis'in ofis saatlerine her hafta katılmaya başladı ve neredeyse her zaman gelen tek öğrenci oydu. Azmi meyvesini verdi: dersten A aldı ve Hartmanis, ertesi dönem ona bağımsız bir araştırma projesinde danışmanlık yapmayı kabul etti. Haftalık toplantıları, Williams'ın üniversite hayatı boyunca devam etti. Hartmanis, karmaşıklık araştırmalarına bireysel bir yaklaşım geliştirmesi için onu cesaretlendirdi ve onu çıkmaz sokaklardan nazikçe uzaklaştırdı.

Williams, "O zamanlar ondan çok etkilenmiştim," dedi. "Sanırım şimdi de öyleyim."

Ancak Williams, Ulusal Bilim Vakfı'ndan çok arzu edilen bir lisansüstü araştırma bursu kazanmasına rağmen, başvurduğu tüm doktora programlarından reddedildi. Hartmanis haberi duyar duymaz bir meslektaşını aradı, ardından dönüp Williams'ı Cornell'de bir yıllık bir yüksek lisans programına kabul edildiği için tebrik etti. Bir yıl sonra Williams tekrar çeşitli doktora programlarına başvurdu ve bu ek araştırma deneyimiyle başarıya ulaştı.

Williams, lisansüstü eğitiminde ve sonraki yıllarda karmaşıklık teorisi üzerine çalışmaya devam etti. 2010 yılında, doktorasını aldıktan dört yıl sonra, teorik bilgisayar bilimindeki en ünlü soru olan zor problemlerin doğasını çözme yolunda küçük ama onlarca yıldır atılan en büyük adım olan bir dönüm noktası sonucunu kanıtladı. Bu sonuç, Williams'ın itibarını pekiştirdi ve karmaşıklık teorisindeki farklı konularda düzinelerce makale daha yazdı.

P ve PSPACE bunlardan biri değildi. Williams, üniversitede ilk karşılaştığı sorundan beri bu konuya ilgi duyuyordu. Hatta bilgisayar bilimleri müfredatını mantık ve felsefe dersleriyle desteklemiş, zaman ve uzay üzerine farklı bakış açılarından ilham almaya çalışmış, ancak nafile.

Williams, "Bu konu hep aklımın bir köşesindeydi," dedi. "Bu konuda söyleyecek kadar ilginç bir şey bulamadım."

Geçtiğimiz yıl nihayet beklediği fırsatı buldu.

Williams'ın yeni sonucunun hikâyesi, hesaplamada bellekle ilgili farklı bir soru üzerindeki ilerlemeyle başladı: Son derece sınırlı bir alanda hangi problemler çözülebilir? 2010 yılında, öncü karmaşıklık teorisyeni Stephen Cook ve çalışma arkadaşları, belirli bir eşik değerinin altında bir alan bütçesine sahip herhangi bir algoritma için imkansız olduğunu kanıtladıkları ağaç değerlendirme problemi adlı bir görev icat ettiler. Ancak bir açık vardı. Kanıt, Paul ve meslektaşlarının onlarca yıl önce ortaya attığı aynı sağduyulu varsayıma dayanıyordu: Algoritmalar, zaten dolu olan bir alanda yeni veri depolayamaz.

Karmaşıklık teorisyenleri on yıldan fazla bir süre bu açığı kapatmaya çalıştı. Ardından, 2023'te Cook'un oğlu James ve Ian Mertz adlı bir araştırmacı, ağaç değerlendirme problemini herkesin düşündüğünden çok daha az yer kaplayarak çözen bir algoritma tasarlayarak bu açığı tamamen açtılar. Baba Cook'un kanıtı, veri parçalarının bir algoritmanın belleğinde ayrı yerlerde bulunması gereken çakıl taşları gibi olduğunu varsayıyordu. Ancak ortaya çıktı ki, veri depolamanın tek yolu bu değil. Beame, "Bu çakıl taşlarını aslında birbirlerinin üzerine hafifçe sıkıştırabileceğimiz şeyler olarak düşünebiliriz," dedi.

Cook ve Mertz'in algoritması birçok araştırmacının merakını uyandırdı, ancak ağaç değerlendirme probleminin ötesinde herhangi bir uygulaması olup olmadığı henüz belli değildi. Wigderson, "Kimse bunun zaman ve mekan açısından ne kadar önemli olduğunu görmedi," dedi.

Ryan Williams istisnaydı. 2024 baharında, bir grup öğrenci, Cook ve Mertz'in dersinde bitirme projesi olarak Cook ve Mertz makalesi hakkında bir sunum yaptı. Onların coşkusu, onu daha yakından incelemeye teşvik etti. Bunu yapar yapmaz aklına bir fikir geldi. Cook ve Mertz'in yönteminin aslında alan kullanımını azaltmak için genel amaçlı bir araç olduğunu fark etti. Neden bunu, Hopcroft, Paul ve Valiant tarafından tasarlanana benzer, ama daha iyi, zaman ve mekanı birbirine bağlayan yeni bir evrensel simülasyona güç sağlamak için kullanmayalım ki?

Bu klasik sonuç, belirli bir zaman bütçesine sahip herhangi bir algoritmayı biraz daha küçük bir alan bütçesine sahip yeni bir algoritmaya dönüştürmenin bir yoluydu. Williams, yumuşak çakıl taşlarına dayalı bir simülasyonun, yeni algoritmanın alan kullanımını çok daha küçük hale getireceğini gördü; bu da kabaca orijinal algoritmanın zaman bütçesinin kareköküne eşitti. Bu yeni alan tasarruflu algoritma aynı zamanda çok daha yavaş olacağından, simülasyonun pratik uygulamaları olması pek olası değildi. Ancak teorik açıdan bakıldığında, devrim niteliğindeydi.

Araştırmacılar, 50 yıl boyunca Hopcroft, Paul ve Valiant'ın evrensel simülasyonunu geliştirmenin imkansız olduğunu varsaymışlardı. Williams'ın fikri -eğer işe yararsa- sadece onların rekorunu kırmakla kalmayacak, aynı zamanda onu yerle bir edecekti.

Williams, "Düşündüm ve 'Bu kesinlikle doğru olamaz' dedim," dedi. Bunu bir kenara bıraktı ve Temmuz ayındaki o kader gününe kadar, argümandaki hatayı bulmaya çalışıp başarısız olana kadar tekrar ele almadı. Hiçbir kusur olmadığını fark ettikten sonra, mümkün olduğunca açık hale getirmek için aylarca kanıtları yazıp yeniden yazdı.

Şubat ayının sonunda Williams nihayet tamamlanmış makaleyi internete koydu . Cook ve Mertz de herkes kadar şaşırmıştı. Mertz, "Başka bir şey yapmadan önce uzun bir yürüyüşe çıkmam gerekti," dedi.

Valiant, sabah işe giderken Williams'ın on yıllar önceki sonucuna göre kaydettiği ilerlemenin ön izlemesini yaptı. Yıllardır, Williams'ın MIT'deki ofisinin hemen aşağısında bulunan Harvard Üniversitesi'nde ders veriyor. Daha önce tanışmışlardı, ancak sonuçların açıklanmasından birkaç hafta önce, karlı bir Şubat günü otobüste karşılaşana kadar aynı mahallede yaşadıklarını bilmiyorlardı. Williams, şaşkın Valiant'a kanıtını anlattı ve makalesini göndereceğine söz verdi.

Valiant, "Çok, çok etkilendim," dedi. "Son 50 yılın en iyi matematiksel sonucunu elde ediyorsanız, bir şeyleri doğru yapıyorsunuz demektir."

Williams, yeni simülasyonuyla uzayın hesaplama gücü hakkında olumlu bir sonuç kanıtlamıştı: Nispeten az alan kullanan algoritmalar, biraz daha fazla zaman gerektiren tüm problemleri çözebilir. Ardından, sadece birkaç satır matematik kullanarak bunu tersine çevirdi ve zamanın hesaplama gücü hakkında olumsuz bir sonuç kanıtladı: Uzaydan daha fazla zaman kullanılmadığı sürece en azından birkaç problem çözülemez. Bu ikinci, daha dar kapsamlı sonuç, araştırmacıların beklentileriyle uyumlu. İşin tuhaf yanı, Williams'ın bu noktaya nasıl ulaştığı: İlk olarak, hangi problemleri çözerlerse çözsünler, tüm algoritmalar için geçerli olan bir sonucu kanıtladı.

Williams, "Buna inanmakta hâlâ güçlük çekiyorum," dedi. "Gerçek olamayacak kadar iyi görünüyor."

Nitel terimlerle ifade edildiğinde, Williams'ın ikinci sonucu, P ve PSPACE problemine uzun zamandır aranan bir çözüm gibi görünebilir. Aradaki fark ölçek meselesidir. P ve PSPACE çok geniş karmaşıklık sınıflarıyken, Williams'ın sonuçları daha incelikli bir düzeyde işliyor. Williams, uzayın gücü ile zamanın gücü arasında nicel bir fark olduğunu ortaya koydu ve PSPACE'in P'den daha büyük olduğunu kanıtlamak için araştırmacıların bu farkı çok daha genişletmeleri gerekecek.

Bu, kaldırımdaki bir çatlağı levye ile Büyük Kanyon kadar genişleyene kadar açmaya benzer, göz korkutucu bir meydan okuma. Ancak Williams'ın simülasyon prosedürünün, önemli adımı defalarca tekrarlayan ve her seferinde biraz yerden tasarruf sağlayan değiştirilmiş bir versiyonunu kullanarak bunu başarmak mümkün olabilir. Bu, levyenizin uzunluğunu tekrar tekrar artırmanın bir yolu gibi; yeterince büyük yapın, her şeyi açabilirsiniz. Bu tekrarlanan iyileştirme, algoritmanın mevcut sürümüyle çalışmıyor, ancak araştırmacılar bunun temel bir sınırlama olup olmadığını bilmiyorlar.

Valiant, "Bu, nihai bir darboğaz olabilir veya 50 yıllık bir darboğaz olabilir," dedi. "Ya da belki gelecek hafta birinin çözebileceği bir şey olabilir."

Sorun gelecek hafta çözülürse, Williams kendine kızacak. Makaleyi yazmadan önce, aylarca sonucunu genişletmeye çalışıp başarısız olmuştu. Ancak böyle bir genişletme mümkün olmasa bile, Williams daha fazla uzay araştırmasının ilginç bir noktaya, belki de bambaşka bir sorunda ilerlemeye yol açacağından emin.

"İspatlamak istediğim şeyleri asla tam olarak ispat edemem," dedi. "Ama çoğu zaman ispatladığım şey, istediğimden çok daha iyi oluyor."

Editörün notu: Scott Aaronson, Quanta Magazine'in danışma kurulu üyesidir.

Orijinal hikaye , Simons Vakfı'nın editöryal olarak bağımsız bir yayını olan Quanta Magazine'den izin alınarak yeniden basılmıştır. Vakfın misyonu, matematik, fizik ve yaşam bilimlerindeki araştırma gelişmelerini ve trendlerini ele alarak kamuoyunun bilim anlayışını geliştirmektir.