YZ, Üstel Zaman Varsayımını Çürütüyor: Tüm Bunlar Ne Anlama Geliyor

OpenAI ve Anthropic, üstel zaman varsayımının yanlış olduğunu gösteren birer kanıt yayımladı.

ETH, kuramsal bilgisayar biliminde 27 yıllık bir varsayım ve bazı problemlerin kaba kuvvetten çok daha hızlı çözülemeyeceğini öne sürer. Şimdi ise önde gelen yapay zekâ laboratuvarları bunun doğru olmadığını söylüyor.

Kanaat geçerli olursa, bu sonuç bugüne kadar bilgisayar bilimindeki en önemli yapay zekâ kaynaklı bulgu olacak. Ayrıca, ETH'yi doğru kabul eden yüzlerce araştırma makalesinin yeniden değerlendirilmesini zorunlu kılıyor.

Bu yazıda, üstel zaman varsayımının gerçekte ne anlama geldiğini ve ilişkili olan P ile NP'yi açıklıyoruz. Ayrıca iki laboratuvarın tam olarak ne iddia ettiğine, kanıtların nasıl denetlendiğine ve kriptografi için nelerin değiştiğine (ve değişmediğine) bakacağız.

Sade Dille P ile NP

P ile NP, cevabı kolayca doğrulanabilen her problemin aynı zamanda kolayca çözülüp çözülmediğini sorar. Bu, Yedi Milyon Ödüllü Problemlerden biridir ve bu haberin ardından da hâlâ açık durumdadır.

Sudoku klasik örnektir. Doldurulmuş bir ızgarayı kontrol etmek saniyeler sürer: her satır, sütun ve kutuda tekrar var mı diye tararsınız. Buna karşın, boş sayılabilecek bir ızgaradan çözümü bulmak çok daha uzun sürebilir ve ızgara büyüdükçe bu fark katlanır.

• P, bir bilgisayarın girdi boyutu n büyüdükçe iş yükü n^², n^³ gibi polinomik biçimde artacak şekilde çözebildiği problemler sınıfıdır.
• NP, bir bilgisayarın önerilen çözümlerini polinom zamanda doğrulayabildiği problemler sınıfıdır.

P'deki her problem aynı zamanda NP'dedir. Açık soru, tersinin geçerli olup olmadığıdır. Çoğu bilgisayar bilimci P ≠ NP olduğuna inanır; yani bazı problemler temelde doğrulamaya kıyasla çözmesi daha zordur. Modern kriptografi de buna dayanır: şifrelemek kolaydır, ancak anahtar olmadan şifreyi çözmek zor olmalıdır.

Üstel Zaman Varsayımı (ETH) Nedir?

ETH daha keskindir: belirli bir NP probleminin, 3-SAT'ın, algoritma ne kadar akıllıca olursa olsun üstel zaman gerektirdiğini iddia eder. UC San Diego'dan Russell Impagliazzo ve Ramamohan Paturi bunu 1990'ların sonunda önerdi; Francis Zane de temel çalışmaya katkıda bulundu.

3-SAT problemi

3-SAT'ta n adet doğru/yanlış değişken ve bir madde listesi içeren bir formül verilir. Her madde, örneğin "x₁ doğru VEYA x₄ yanlış VEYA x₇ doğru" gibi üç koşulu VEYA ile birleştirir. Görev, tüm maddeleri aynı anda sağlayan bir değişken ataması bulmaktır.

Kaba kuvvet yaklaşımı tüm 2ⁿ atamayı dener; bu nedenle her ek değişken işi iki katına çıkarır. Yaklaşık 100 değişken civarında bunun umutsuz olduğunu görebilirsiniz.

ETH ne söyler

ETH, c > 1 olacak bir sabit olduğunu ve hiçbir algoritmanın 3-SAT'ı cⁿ'den daha hızlı çözemeyeceğini söyler. Zekice algoritmalar tabanı 2'nin altına indirebilir, ancak hiçbir zaman tümüyle üseldışı (subexponential) seviyeye inemez. Resmî olarak: δ > 0 olacak şekilde 3-SAT'ın O(2^δn) zamanda çözülemeyeceğini iddia eder.

On yıllar boyunca ilerleme bu tabloyla uyumluydu. Araştırmacılar tabanı tıraşlamaya devam etti, ancak 1'in epey üzerinde kaldı. 3-SAT pek çok başka probleme dönüştürülebildiği için ETH, temel bir varsayım haline geldi. Araştırmacılar, Clique, Vertex Cover, Independent Set ve diğer problemler için de çok daha hızlı çözülemeyeceğini savunmakta kullandı. 

Yeni sonuç nasıl karşılaştırılır

Yeni üst sınır kısaca 2^o(n) diye yazılır. Eklenen her değişken başına maliyet, n arttıkça 1'e yaklaşır; bu da ETH'nin imkânsız dediği şeydir.

OpenAI ve Anthropic Ne Duyurdu

Her iki laboratuvar da özünde aynı üseldışı üst sınıra bağımsız olarak ulaştı ve her ikisi de makalelerini Lean ispat asistanında makineyle denetlenmiş kanıtlarla destekledi.

Anthropic, Claude'un çekirdek algoritmayı yaklaşık 14 milyon token çıktı ürettikten sonra hiçbir insan girdisi olmadan bulduğunu söylüyor. Yöntemi tensör ağları ve rank argümanları kullanıyor. Araştırmacılar daha sonra nihai makaleye yardımcı oldu.

Neden her iki laboratuvar da aynı gün buldu?

Hiçbir laboratuvar zamanlamayı açıklamadı. Anthropic'in makalesi iki sonucu bağımsız ve eşzamanlı olarak niteliyor ve iki yazım, özünde aynı üst sınıra ulaşmak için matematikte farklı yollar izliyor. 

Bazı bağlamlar bu çakışmayı ilk bakışta göründüğünden daha az şaşırtıcı kılıyor. Her iki laboratuvar da modellerini uzun açık problem listelerine yönlendiriyor ve OpenAI tek başına Ekim başında yüzlerce yapay zekâ kaynaklı matematik elyazması yayımladı. ETH, alandaki en bilinen hedeflerden biridir ve her iki model de aynı yayımlanmış çalışmalardan öğrenmiştir. Bağımsız, eşzamanlı keşif bilimde eski bir kalıptır; kalkülüste Newton ve Leibniz ya da doğal seçilimde Darwin ve Wallace gibi.

Kanıtlar ne kadar sağlam?

Lean, biçimsel bir ifadenin aksiyomlarından mantıksal olarak çıktığını teyit eder. Biçimsel ifadenin makaleyle aynı şeyi söylediğini teyit edemez. Anthropic, bu eşleşmeyi hiçbir makinenin kontrol etmediğini not ediyor ve OpenAI, Lean dosyasının manşettekinden biraz daha zayıf bir üst sınırı ispatladığını söylüyor.

Şimdi, problemi öneren aynı araştırmacılar, Impagliazzo ve Paturi, MIT'den Ryan Williams ile birlikte, biçimsel ifadelerin gerçekten ETH'yi yakalayıp yakalamadığını değerlendirmek için çalıştaylar düzenliyor. Mektupları, incelemeye katılmanın bir onay anlamına gelmediğini vurguluyor. Bu makale yazıldığı sırada, herkesin üzerinde uzlaştığı bir hata kamuya açık olarak bulunmamıştı. 

Williams, OpenAI'nin kanıtının bazı bölümlerinin rutin göründüğünü, ancak "iki ya da üç uzaylı görünümlü bölümün" hâlâ incelemeye ihtiyaç duyduğunu söyledi. ETH'nin yazarlarından Impagliazzo ise sonucu derinden şaşırtıcı olarak nitelendirdi.

Neler Değişiyor, Neler Değişmiyor

Uygulamada bugün neredeyse hiçbir şey değişmiyor (oh olsun): yeni algoritmalar yalnızca herhangi bir bilgisayarın asla tutamayacağı kadar büyük girdilerde kaba kuvveti yeniyor.

Daha hızlı SAT çözücüleri yok

Anthropic’in makalesi, yönteminin yalnızca astronomik büyüklükteki girdilerde kaba kuvveti geçtiğini söylüyor. Değişken başına beş madde içeren tipik formüller için eşik noktası yaklaşık 10.000 basamaklı bir sayı. En genel durumda ise yaklaşık 100 milyon basamaklı bir sayı. 

Yazarlar ayrıca yaklaşımlarının yaklaşık 10 milyon değişkenin altındaki hiçbir şeye yardımcı olmasının olası olmadığını söylüyor. Çip doğrulama, çizelgeleme ve planlamada kullanılan SAT çözücüleri bu sonuçtan hızlanmayacak.

Kriptografi bozulmadı

Sonuç P ile NP'ye dokunmuyor. Kimse bunu iddia etmiyor. OpenAI, algoritmanın gerçek kriptosistemleri kırıp kırmadığını kontrol ettiğini ve kırmadığından oldukça emin olduğunu söylüyor. 

Kuram yeniden yazılıyor

Daha büyük etki araştırmada olacak. ETH veya SETH üzerine kurulu zorluk sonuçlarının şimdi yeni bir dayanağa ihtiyacı var ve bazı araştırmacılar yıllara yayılan kendi çalışmalarının gözden geçirilmesi gerekeceğini söylüyor. Ancak her şey yıkılmıyor. Anthropic, sonucun birçok ince taneli karmaşıklık sonucunu destekleyen orthogonal vectors problem'i çürütmediğini belirtiyor. 

Yapay Zekâ İçin Neden Önemli

Başlık, 3-SAT'tan çok, yanıtı kimin bulduğuyla ilgili: iki yapay zekâ sistemi, uzmanların bir nesildir güvendiği bir varsayımı bağımsız olarak tersine çevirdi.

Araştırma iş ortağı olarak yapay zekâ

Araştırmacılar artık her hafta ya da iki haftada bir yeni yapay zekâ sonuçlarının geldiğini, devam eden projeleri de altüst ettiğini anlatıyor. Lean gibi biçimsel araçlar, insanların uzun bir makine yazımı kanıta her satırı yeniden türetmeden güvenmesini sağladığı için merkezi hale geliyor.

Gizli kestirmeler ve öz-iyileştirme

ETH, bazı arama problemlerinin akıllı bir kestirmesi olmadığına dair bir inancı yakalıyordu. Eğer bu inanç yanlışsa, bariz şekilde zor olan diğer problemler de kestirmeler barındırabilir.

Ben, özyinelemeli öz-iyileştirme için bu tür kestirmelerin çok önemli olabileceği bir alan olarak algoritma keşfini düşünüyorum; bu, daha iyi yapay zekâ tasarlamaya yardımcı olan yapay zekâ sistemleri fikridir. Yapay zekâyı daha hızlı algoritmalar bulmak için kullanmak buna giden somut bir yol; ancak bu sonuç bugün doğrudan bunu yapmıyor.

Veri profesyonelleri için ne anlama geliyor

Veriyle üretim yapanlar için üç ders öne çıkıyor:

• Karmaşıklık kuramı sadece akademik değil: Bir problemin NP-zor olduğunu bilmek, kesin arama yerine ne zaman sezgisel yöntemler, yaklaşımlar veya çözücüler düşünmeniz gerektiğini gösterir.
• Doğrulama bir beceridir: Yapay zekâ daha fazla kod ve analiz ürettikçe, çıktısını kontrol etmek (testlerle, kanıtlarla veya tekrarlanabilir boru hatlarıyla) üretmek kadar önem kazanır.
• Asimptotikler yanıltabilir: Kuramda "daha hızlı" olan bir algoritma, gerçek dünya boyutlarında işe yaramayabilir. 

Sonuç

Eğer kanıtlar uzman incelemesinden sağ çıkarsa, üstel zaman varsayımı, yanlış olduğu ortaya çıkan yaygınca kabul görmüş varsayımların kısa listesine katılacak (örneğin Euler’in kuvvetler toplamı varsayımı gibi). Ancak P ile NP hâlâ açık ve kriptografi şimdilik güvende.

Takip edilecek bir sonraki dönüm noktaları, ETH'nin orijinal yazarlarının yürüttüğü inceleme çalıştayları, algoritmaların bağımsız yeniden uygulamaları ve birilerinin üst sınırı daha da sıkılaştırıp sıkılaştıramayacağıdır.

Bu tür haberlerin arkasındaki temelleri inşa etmek için veri yapıları ve algoritmalar, Python programlama ve makine öğrenmesi kurslarımızı keşfedin. Bu kurslar, bu tür sonuçları okunabilir kılan Büyük-O düşüncesini kapsar.