Hayır, ne OpenAI ne de Anthropic P = NP’yi kanıtladı. İki laboratuvar da 3-SAT için üstelden hızlı ama polinomdan çok yavaş birer algoritma iddia ediyor, bu doğruysa Üstel Zaman Hipotezi’ni (ETH) çürütür, P NP sorusunu ise açık bırakır ve Clay ödülü hâlâ sahipsiz kalır.
Bu yazıda önce P ve NP’nin ne olduğunu kuruyorum, sonra Ekim 2026 sonunda gelen iki sonucun tam olarak neyi iddia ettiğine geçiyorum. Tarihler ve laboratuvar laboratuvar ayrıntılar için ETH iddialarının ayrıntılı haber analizi yazıma bakabilirsiniz.
P NP problemi nedir, gündelik dille?
P NP problemi şunu soruyor: Çözümü kolayca kontrol edilebilen her problem, kolayca çözülebilir mi? Soruyu 1971’de Cook ve Levin birbirinden bağımsız olarak ortaya koydu. Clay Matematik Enstitüsü de bu soruyu Milenyum Ödülü problemleri arasında sayıyor.
Üç haneli şifreli bir bavul kilidi düşünün. Biri size doğru şifreyi söylerse, çevirip açılıp açılmadığına bakmanız birkaç saniye sürer. Şifreyi bilmiyorsanız 000’dan 999’a kadar denemeniz gerekebilir. Hane sayısı arttıkça kontrol hâlâ tek hamle, arama ise katlanarak büyüyor.
Fakültenin sınav takvimi de böyle. Hazır bir takvimde çakışma olup olmadığına hızla bakarsınız, binlerce öğrenci için takvimi sıfırdan kurmak ise çok daha zor.
Clay’in kendi örneği bir yurtla ilgili. 400 başvurandan 100 öğrenci seçeceksiniz ve elinizde birlikte yerleştirilemeyecek çiftlerin listesi var. Önerilen bir listeyi kontrol etmek kolay. Bütün 100 kişilik grupları tek tek denemek ise imkânsız, çünkü sayıları akıl almaz derecede büyük.
Karmaşıklık kuramında “kolay” kelimesinin net bir karşılığı var: polinom zaman. Girdinin boyutu n ise, polinom zamanlı bir yöntem kabaca n2, n3 ya da n’nin sabit bir kuvveti kadar adım atar. Buradan iki sınıf çıkıyor:
- P, polinom zamanda çözülebilen problemlerin sınıfı.
- NP, önerilen bir cevabın polinom zamanda kontrol edilebildiği problemlerin sınıfı.
P’deki her problem NP’de de yer alır, çünkü çözebiliyorsanız kontrol de edebilirsiniz. Asıl soru bu iki sınıfın aynı olup olmadığı. Bunu iki yönde de kanıtlayan çıkmadı.
NP-complete ve 3-SAT ne demek?
NP’nin içinde, sınıftaki her şey kadar zor olan problemler var. Bunlardan birini hızlı çözebilirseniz NP’deki her problemi hızlı çözersiniz, çünkü her NP problemi verimli biçimde ona çevrilebilir. Bu problemlere NP-complete (Türkçede NP-tam) deniyor.
En bilinen örnek 3-SAT. Bir doğum günü partisi için davet listesi hazırladığınızı düşünün. Her arkadaş için tek bir değişken var: gelsin ya da gelmesin. Elinizde de şöyle koşullar var:
- Ayşe gelsin ya da Can gelmesin ya da Deniz gelsin.
- Can gelsin ya da Ece gelsin ya da Ayşe gelmesin.
Her koşul üç kişiden söz ediyor ve en az birinin sağlanması yetiyor. Bütün koşulların aynı anda sağlandığı bir davet listesi var mı? İşte 3-SAT bu. Biçimsel hâliyle n tane doğru ya da yanlış değişken, üçer terimli VEYA koşulları ve bu koşulları bağlayan VE’lerden oluşan bir formül.
Bir listeyi kontrol etmek kolay, koşullara bir kez bakarsınız. Uygun listeyi kaba kuvvetle aramak ise 2n olasılığı denemek demek, yani her yeni arkadaşla iş iki katına çıkıyor.
3-SAT’ın NP-complete olduğu Cook (1971) ve Karp (1972) çalışmalarıyla biliniyor. Bu da büyük soruyu tek bir probleme bağlıyor: P = NP, ancak ve ancak 3-SAT için polinom zamanlı bir algoritma varsa doğru.
Ekim 2026’dan önceki en iyi algoritmalar hâlâ üsteldi, yalnızca tabanları küçülmüştü. Anthropic’in makalesinde anılan rekorlar, deterministik algoritmalar için O(1,328n) (Liu, 2018) ve rastgele algoritmalar için O(1,308n) (PPSZ çizgisi).
Üstel Zaman Hipotezi (ETH) neden P NP ile aynı soru değil?
Impagliazzo ve Paturi’nin Zane ile birlikte ortaya koyduğu Üstel Zaman Hipotezi, 3-SAT’ın bir δ > 0 sabiti için 2δn zaman gerektirdiğini söylüyor. Bu, P ≠ NP’den daha iddialı bir varsayım, çünkü 3-SAT’ı aşağıdaki merdivenin en üst basamağına sabitliyor:
- Polinom, örneğin n3. P sınıfı burası.
- Alt üstel, örneğin 2n / √(log n). Her 2δn‘den hızlı, her polinomdan yavaş.
- Üstel, örneğin 2δn ya da 1,3n. ETH, 3-SAT’ın burada kaldığını söylüyordu.
Farkı hissetmek için Clay örneğindeki sayıyı alalım, n = 400 değişken olsun ve sabitleri yok sayalım. n3 yaklaşık 64 milyon adım. Ortadaki temsilî biçim yaklaşık 2136, yani kabaca 1041. Kaba kuvvetin 2400‘ü ise kabaca 10120. Orta basamak tepeye göre muazzam bir iyileşme, ama hiçbir bilgisayarın bitiremeyeceği kadar büyük.
Mantık tek yönde işliyor. P = NP ise 3-SAT polinomdur ve ETH yanlış olur. Ama ETH’nin yanlış çıkması P = NP demek değil. Yeni sonuçlar 3-SAT’ı üçüncü basamaktan ikinciye indiriyor. Birinci basamağa indirmek P NP sorusunun kendisi ve ona dokunulmadı.
OpenAI ya da Anthropic P = NP’yi kanıtladı mı?
Hayır. İki laboratuvar da böyle bir şey söylemiyor. İkisinin iddiası daha dar ama yine de çarpıcı: 3-SAT, 2o(n) zamanda çözülebilir. Yani üs, n’nin herhangi bir sabit katından daha yavaş büyüyor.
OpenAI’ın 26 Ekim 2026 tarihli yazısına göre sistemleri ETH’nin yanlış olduğunu kanıtladı ve sonuç ardından Lean’de doğrulandı (“our system has recently proved that the ETH is false, a result that was subsequently verified in Lean”). OpenAI’a göre çürütme 16 Ekim’de bulundu, Lean biçimselleştirmesi 17 Ekim’de geldi. Çalışmaya UCSD’den Impagliazzo ve Paturi ile MIT’den Ryan Williams rehberlik etti. OpenAI, ETH’yi “deeply related to the P vs. NP problem” (P NP problemiyle derinden bağlantılı) diye tanımlıyor ve pratik iyileşmelerin “will require significant further research” (ciddi ek araştırma gerektireceğini) söylüyor.
Anthropic’in makalesinin adı “A 2^{o(n)} Time Algorithm for 3-SAT”, yazar olarak “Claude (Anthropic)” yazıyor ve tarihi 26 Ekim 2026. Makale açıkça şunu söylüyor: “our result does not bear on the P vs NP question directly, nor does it yield any practical algorithms for NP-complete problems.” Yani sonuç P NP sorusuna doğrudan dokunmuyor ve NP-complete problemler için pratik bir algoritma da vermiyor. README de sonucun tamamen asimptotik olduğunu ve formülleri pratikte çözmek hakkında bir şey söylemediğini ekliyor (“purely asymptotic and says nothing about solving formulas in practice”).
| Laboratuvar | İddia | Belirtilen çalışma süresi | Göstermediği şey |
|---|---|---|---|
| OpenAI (sonuç 378, “The Exponential Time Hypothesis is False” ön baskısı, 25 Ekim 2026 tarihli) | Her sabit k ≥ 2 için bir k-CNF formülünün sağlayan atamalarını polinom bellekle sayan deterministik bir algoritma. Ayrıca ENP içindeki bir dil için süperlineer devre alt sınırları | (n+m)O_k(1) · 2n / (log n)1/2 + o(1) | Polinom zamanlı bir algoritma, dolayısıyla P NP’ye bir cevap. Henüz pratik bir hızlanma da yok |
| Anthropic (“A 2^{o(n)} Time Algorithm for 3-SAT”, 26 Ekim 2026 tarihli) | #3-SAT’ı, yani sağlayan atamaları saymayı çözen deterministik bir algoritma, Lean 4’te kontrol edilmiş | 2O(n log log n / √(log n)) | Makalenin kendi ifadesiyle P NP sorusuna doğrudan bir katkı ya da NP-complete problemler için pratik bir algoritma |
İki süre de alt üstel ve ikisi de her polinomdan çok uzak. Hikâyenin özü bu aralıkta.
Lean neyi doğrular, neyi doğrulayamaz?
Lean bir ispat asistanı. Çekirdek denen küçük ve güvenilir bir program, biçimsel ispatın her adımını kontrol ediyor. Çekirdek kabul ederse ispat, biçimsel ifadeye göre doğrudur.
Anthropic, Lean 4 v4.33.1 sürümünü Mathlib ile sabitledi ve Comparator aracıyla ikinci bir çekirdek olan nanoda’yı da çalıştırdı. Böylece aynı ispatı iki ayrı denetleyici kabul etti. OpenAI ise çürütmenin, sistemin onu bulduğu günün ertesinde, 17 Ekim’de Lean’e döküldüğünü söylüyor. Bu tarih 12 ile 18 Ekim haftalık yazımın kapsadığı haftaya denk geliyor. OpenAI ön baskısının tarihi olan 25 Ekim de ispatların geldiği haftanın son günü.
Lean’in yapamadığı şey, biçimsel ifadenin İngilizce makalenin iddia ettiği şeyi gerçekten söyleyip söylemediğini kontrol etmek. Anthropic’in README’si bunu açıkça yazıyor: “Lean checks the proofs, but no machine checks that this file says what the paper says.” Lean ispatları kontrol ediyor, ama dosyanın makaledeki şeyi söylediğini hiçbir makine kontrol etmiyor. Tanımda küçük bir kayma ya da manşetten zayıf bir teorem çekirdekten sorunsuz geçer. Lean bir sonucun pratik olup olmadığını da söylemez. Bu sınırları OpenAI’ın matematik sonuçları ve Lean yazımda daha uzun anlattım.
Kısacası Lean onayı, matematiğin Lean’de yazıldığı hâliyle sağlam olduğuna dair güçlü bir kanıt. İfadeyi makaleyle karşılaştırmak ise hâlâ insanların işi.
P = NP çıksaydı kripto ve yapay zekâ için ne değişirdi?
Burada kripto derken kriptografiyi, yani şifrelemeyi kastediyorum. Bilgisayar güvenliğinin önemli bir kısmı, kontrolü kolay ama çözümü zor sayılan problemlere dayanıyor. Bir dijital imzayı doğrulamak hızlıdır, sahtesini üretmenin ise pratikte imkânsız olması beklenir. P = NP, yapıcı ve düşük dereceli bir algoritmayla kanıtlansaydı, bu problemlerin birçoğu pratikte çözülebilir hâle gelebilirdi.
Çekinceler önemli. İspat yapıcı olmayabilir, yani algoritmanın var olduğunu gösterip onu vermeyebilir. Ya da algoritma n100 gibi bir sürede çalışabilir, kâğıt üzerinde polinom ama pratikte işe yaramaz. Ekim 2026 sonuçları ise polinom bile değil. Anthropic makalesi NP-complete problemler için pratik bir algoritma vermediğini söylüyor, OpenAI de pratik iyileşmenin ciddi ek araştırma gerektirdiğini belirtiyor. Bu sonuçların hiçbiri şifre kırmaya yarayan bir araç değil.
Yapay zekâ tarafında bağlantı iki yönlü. Planlama ve çizelgeleme gibi işler de kontrolü kolay, bulması zor işler, pratik bir P = NP algoritması yazılımın yapabileceklerini değiştirirdi. Öbür yönde ise bu kez sonuçları yapay zekâ üretti. OpenAI çürütmeyi kendi sisteminin bulduğunu söylüyor, Anthropic de yazar olarak Claude’u gösteriyor. Makine üretimi ispatlara güven meselesi de yukarıdaki Lean bölümüne bağlanıyor.
Sık sorulan sorular
P NP problemi çözüldü mü?
Hayır. OpenAI ve Anthropic’in Ekim 2026 sonuçları 3-SAT için alt üstel algoritmalar veriyor ve doğruysa Üstel Zaman Hipotezi’ni çürütüyor. P = NP için polinom zamanlı bir algoritma, P ≠ NP için de henüz kimsenin bulamadığı bir alt sınır gerekiyor. Clay ödülü sahipsiz.
OpenAI 3-SAT için ne buldu?
OpenAI’ın 378 numaralı sonucu, her sabit k ≥ 2 için k-CNF formüllerinin sağlayan atamalarını (n+m)O_k(1) · 2n / (log n)1/2 + o(1) sürede ve polinom bellekle sayan deterministik bir algoritma. Bu alt üstel bir süre, polinom değil.
Üstel Zaman Hipotezi (ETH) nedir?
Impagliazzo ve Paturi’nin Zane ile birlikte ortaya koyduğu hipotez, 3-SAT’ın bir δ > 0 sabiti için 2δn zaman gerektirdiğini söylüyor. P ≠ NP’den daha güçlü bir iddia. Çürütülmesi 3-SAT’ın gerçek üstelden hızlı çözülebildiğini gösterir, polinom zamanda çözülebildiğini değil.
P = NP olursa şifreler kırılır mı?
Ancak algoritma yapıcı ve düşük dereceli olursa pratikte bir tehdit doğar. Yapıcı olmayan bir ispat ya da n100 gibi bir algoritma kuramı değiştirir ama şifrelemeyi hemen etkilemez. Ekim 2026 sonuçları ise polinom bile değil.
P NP problemini çözene ödül var mı?
Evet. P NP, Clay Matematik Enstitüsü’nün Milenyum Ödülü problemlerinden biri. Clay her problemin çözümü için 1 milyon ABD doları ayırdı ve P NP ödülü hâlâ sahipsiz.
NP-complete ne demek?
NP içinde olup NP’deki her problemin verimli biçimde kendisine çevrilebildiği problemler. Birini polinom zamanda çözen, hepsini çözmüş olur. 3-SAT bunun en bilinen örneği.
