AI, 25 yıllık varsayımı çürüttü: P vs NP nedir?

Geçen ay OpenAI ve Anthropic, karmaşıklık teoristlerinin 1999'dan beri üzerine inşa ettikleri bir varsayımı yıktı. Exponential Time Hypothesis (ETH) diye bilinen bu hipotez artık geçerli sayılmıyor. Ama bu şu demek değil: şifreler kırıldı, P vs NP çözüldü ya da internet güvenliği çöktü. Gerçekte neler değiştiğini anlamak için P vs NP'den başlamak gerek.

P vs NP'nin özü basit bir fark: bir sorunun cevabını hızlı mı kontrol edebilirsin, yoksa cevabı bulmak mı zor? Örneğin 3-SAT problemi. Sana bir mantık denklemi veriyorum: (a ∨ b ∨ c) ∧ (¬a ∨ d ∨ e) ∧ (¬c ∨ f ∨ g). Her harfi doğru ya da yanlış yaparak tüm parantezleri tatmin etmen gerekiyor. Birinin cevabını kontrol etmek kolay, tek bir geçiş. Ama cevabı bulmak? 50 değişken varsa 2⁵⁰ (yaklaşık bir katrilyon) kombinasyonu test etmen gerek.

OCak öncesi en iyi algoritma PPSZ, bunu 1.307ⁿ'e indiriyordu. Yine üstel, ama daha hızlı. ETH, bu tür problemler için hiçbir algoritmanın 2ⁿ'den önemli ölçüde daha hızlı olamayacağını iddia ediyordu. Kaynağa göre, OpenAI'nin modeli bunu çürüttü, ETH yanlış olduğunu gösteren bir kanıt buldu ve Lean proof checker ile kısmen doğrulandı.

Bu, şifreyi kırmadığı anlamına gelir. P vs NP hâlâ açık. Ama demektir ki, özel problemler için çok daha akıllı algoritmalar mümkün olabilir. Teorik bilgisayar biliminin temellerinden biri sarsıldı, ve AI bunu buldu.