OpenAI üstel zaman hipotezinin yanlış olduğunu söylüyor: 3-SAT, ETH ve bu iddia neden bu kadar büyük?

Ne oldu?

OpenAI 26 Ekim’de, bir iç modelinin üstel zaman hipotezini (Exponential Time Hypothesis, kısaca ETH) çürüttüğünü açıkladı. Şirkete göre model kanıtı 16 Ekim’de buldu, ertesi gün de kanıt Lean ile makineye kontrol ettirildi. Makale “The Exponential Time Hypothesis is False” başlığıyla, yazar olarak yalnızca “OpenAI” yazılı şekilde openai/math deposunda yayınlandı. Aynı gece Anthropic de Claude’a atfedilen, benzer sonuçlu kendi makalesini paylaştı.

Two Minute Papers videosu konuyu kedi ve köpek örnekleriyle anlatıyor. Biz teknik ayrıntıları makalenin kendisinden ve alanın uzmanlarının yazdıklarından kontrol ettik.

3-SAT nedir?

Elinde evet/hayır değeri alan değişkenler var: “kedi uyuyor”, “köpek havlıyor” gibi. Bir de kurallar listesi var, her kural en fazla üç koşulun veya’sı: “kedi uyuyor ya da köpek havlıyor ya da robot dans ediyor”. Soru şu: Bütün kuralları aynı anda doğru yapan bir atama var mı? Buna 3-SAT deniyor.

Kontrol etmek kolay: Bir atama verirsen kuralları tek tek gezip bakarsın. Bulmak zor: n değişken için 2ⁿ ihtimal var. 3-SAT, P ve NP yazımızda anlattığımız NP-tam problemlerin atası. Rota planlamadan frekans atamaya kadar pek çok problem ona dönüştürülebiliyor.

ETH ne diyordu?

Akıllı algoritmalar 2ⁿ’den iyisini yapıyor. Bilinen en iyileri 3-SAT’ı kabaca 1,3ⁿ adımda çözüyordu. Ama taban hep üstel kaldı: Değişken sayısı biraz artınca iş katlanarak büyüyor.

Russell Impagliazzo ve Ramamohan Paturi 2001’de bunun kaçınılmaz olduğunu varsaydı. ETH’ye göre 3-SAT’ı, bir c > 0 için 2^(cn)’den hızlı çözmenin genel bir yolu yok. Kanıtlanmış değildi ama o kadar makul görünüyordu ki, onlarca problem için “bundan daha hızlı algoritma yoktur” sonuçları bu varsayımın üzerine kuruldu. Bunların daha güçlü bir versiyonu olan SETH, ince taneli karmaşıklık (fine-grained complexity) denen bütün bir alanın temeliydi.

Makale ne iddia ediyor?

OpenAI’ın algoritması 3-SAT’ı çözmekle kalmıyor, formülü sağlayan atamaların sayısını da tam olarak buluyor. Deterministik, polinom bellekle çalışıyor. Süresi kabaca 2 üzeri n·log log n / √log n. Buradaki kritik nokta paydadaki √log n: Üs, n’den yavaş büyüyor. Yani algoritma “üstelin altında” (subexponential) kalıyor ve ETH’nin “bundan hızlısı yok” dediği sınırı geçiyor. SETH de ETH’yi gerektirdiği için onunla birlikte düşüyor.

Yöntem cebirsel: Sayma problemi polinom denklemlerine çevriliyor, bu denklemler değişken gruplarına ayrılıp ortak ölçümlerle birleştiriliyor. Makale ayrıca graf boyama ve mükemmel eşleşme sayma gibi yan sonuçlar da veriyor.

Ne değildir?

• P = NP çözülmedi. Algoritma hâlâ polinom zamanlı değil. Makalenin kendisi de bunun genel NP problemlerine üstelin altında algoritma anlamına gelmediğini yazıyor. Fortnow’a göre Subset Sum ya da gezgin satıcı problemi için yeni bir şey yok.
• SAT çözücüler hızlanmayacak. Sabitler açık değil, √log n de inanılmaz yavaş büyüyor: Bir milyon değişkende bile yalnızca 3,7 civarında. Haberlere göre Anthropic’in makalesi de sonucun pratikte formül çözmek hakkında bir şey söylemediğini açıkça yazıyor.
• Eski sonuçlar yanlış olmadı. ETH’ye dayanan alt sınırlar “ETH doğruysa…” diye başlayan koşullu cümlelerdi. Bu cümleler hâlâ doğru, sadece öncülleri artık muhtemelen yanlış.

Kim kontrol ediyor?

Hipotezin sahipleri Impagliazzo ve Paturi, MIT’den Ryan Williams ile birlikte açık ve bağımsız bir inceleme düzenliyor. Açık mektuplarında katılımlarının bir onay anlamına gelmediğini, gizlilik sözleşmesi imzalamadıklarını ve ücret almadıklarını yazıyorlar. Bu arada Ryan O’Donnell ve Shiva Kintali, en iyi sınırı değil en sade anlatımı hedefleyen kendi kanıtlarını yayınladı. Fortnow’a göre Lean sürümü makaledekinden biraz daha zayıf bir sınır kanıtlıyor, ama o da üstelin altında. Fortnow kanıtı kendisi doğrulamadığını söylüyor, yine de “ETH’nin bittiğini varsaymak artık güvenli” diye yazıyor.

Eylül’deki Navier-Stokes iddiasında tartışma “kanıt doğru mu?” kadar “doğru soruyu mu çözdü?” etrafında dönmüştü. Burada soru net tanımlı, bu yüzden inceleme daha hızlı sonuç verebilir.

Düşün

• Bir kanıtı Lean kontrol etti ama hiçbir insan okumadı. Ona ne kadar güvenirsin?
• “Kanıtlanmamış ama herkes doğru sanıyor” denen başka hangi varsayımlara günlük işinde dayanıyorsun?

Kendi cümlelerimizle yazılmış bir özettir, çeviri değildir. Tüm kaynaklar yukarıda.