P vs NP: Bir çözümü kontrol etmek kolaysa, bulmak da kolay mı?

Kontrol etmek ve bulmak

Clay Matematik Enstitüsü’nün örneği şöyle: 400 öğrenci yurtta yer istiyor ama sadece 100 yer var. Elinde bir de “bu ikisi aynı yurtta kalmasın” listesi var. Biri sana 100 kişilik bir liste verirse, kurala uyup uymadığını birkaç dakikada kontrol edersin. Ama böyle bir listeyi sıfırdan bulmak çok daha zor. Olası seçimlerin sayısı evrendeki atom sayısını geçiyor.

P vs NP sorusu tam olarak bu: Bir çözümü hızlıca kontrol edebiliyorsak, onu hızlıca bulabilir miyiz? Clay bu soruyu yedi “Millennium” probleminden biri yaptı. Doğru bir kanıta bir milyon dolar ödül var.

P ve NP ne demek?

Burada “hızlı”, polinom zaman demek. Girdi büyüdükçe iş n, n log n ya da n² gibi makul bir hızla artıyor. Bir isim listesini sıralamak buna örnek: Liste on kat büyürse iş kabaca on, yirmi kat artıyor. Bu şekilde çözülebilen problemlerin sınıfına P deniyor.

NP ise, cevabı “evet” olduğunda bunu hızlıca kontrol edebileceğin bir kanıtı olan problemler. Örneğin büyütülmüş, n²×n² boyutlu bir Sudoku. Doldurulmuş bir tabloyu kontrol etmek kolay. Boş bir tabloyu çözmenin hızlı bir yolunu ise kimse bilmiyor. Her P problemi NP’de de var. Soru, ikisinin aynı küme olup olmadığı.

Videodaki gezgin satıcı örneğinde bir incelik var. 15 şehirde denenecek rota sayısı 14!, yani yaklaşık 87 milyar. Ama “en kısa rota bu” iddiasını kontrol etmek de kolay değil. Bu yüzden problem “X km’den kısa bir rota var mı?” diye sorulur. Bir rota verilirse onu toplayıp kontrol etmek kolay.

NP-tam: Hepsinin anahtarı

Stephen Cook 1971’de NP’nin “en zor” problemlerini tanımladı. Leonid Levin de aynı fikre Sovyetler Birliği’nde bağımsız olarak ulaştı. İlk örnek SAT: Uzun bir mantık ifadesinde değişkenlere doğru/yanlış değerleri vererek ifadeyi doğru yapabilir misin? Cook, NP’deki her problemin hızlı bir dönüşümle (reduction) SAT’a çevrilebildiğini gösterdi. Bir yıl sonra Richard Karp yirmi tanıdık problemin daha aynı sınıfta olduğunu kanıtladı. Bugün bu listede binlerce problem var. Sudoku’nun genel hâli de onlardan biri.

Bunlara NP-tam (NP-complete) deniyor. Önemleri şu: Bir tanesi için hızlı bir algoritma bulunursa, dönüşümler sayesinde hepsi hızlı çözülür ve P = NP olur.

Bir düzeltme: Videoda asal çarpanlara ayırma da bu grupta anlatılıyor. Çarpanlara ayırma NP’de, ama NP-tam olduğu bilinmiyor. Cook’un problem tanımına göre ne P’de ne de NP-tam olması bekleniyor.

Neden kanıtlanamıyor?

Uzmanların çoğu P ≠ NP olduğuna inanıyor. Gasarch’ın 2018 anketinde katılımcıların yüzde 88’i böyle düşünüyordu. Ama kanıt yok, çünkü bilinen yöntemlerin her biri bir duvara çarptı:

• Relativization (1975): Baker, Gill ve Solovay, klasik tekniklerin bu soruyu tek başına çözemeyeceğini gösterdi.
• Natural proofs: Razborov ve Rudich, devre karmaşıklığına dayalı yaygın bir yaklaşımın, güvenli şifreleme varsa işe yaramayacağını gösterdi.
• Algebrization (2008): Aaronson ve Wigderson, ilk duvarı başka sorularda aşmayı başaran cebirsel tekniklerin de bu soruya yetmediğini gösterdi.

Yani bir kanıt, henüz kimsenin bilmediği yeni bir fikir istiyor.

P = NP çıkarsa ne olur?

Cook’a göre 3-SAT’ı n² adımda çözen bir algoritma, 200 basamaklı sayıları dakikalar içinde çarpanlarına ayırabilirdi. Bu da bugünkü şifrelemenin dayandığı varsayımların çoğunu çökertirdi. Öte yandan bilgisayarlar, makul uzunlukta kanıtı olan her teoremin kanıtını bulabilirdi. Kanıtı kontrol etmek kolay, bulmak zor. Bugün yapay zekânın kanıtlarını Lean ile kontrol ettirme fikri de bu farka dayanıyor.

İki uyarı var. P = NP, pratik bir algoritma anlamına gelmeyebilir: n¹⁰⁰ adım da polinomdur. P ≠ NP de şifrelemenin güvenli olduğunu tek başına kanıtlamaz. Cook’un belirttiği gibi, problemler çoğu girdi için kolay çıkabilir.

Fikir yeni de değil. John Nash 1955’te NSA’ya yazdığı mektupta, iyi bir şifreyi kırmanın anahtar uzadıkça üstel olarak zorlaşması gerektiğini ve bunu kanıtlayamayacağını söylemişti. Güncelleme: Ekim 2026’da OpenAI, 3-SAT’ı üstelin altında çözen bir algoritmayla üstel zaman hipotezini çürüttüğünü açıkladı. P = NP’yi çözmüyor (üstel zaman hipotezi yazısı).

Düşün

• Kontrol etmesi kolay ama bulması zor bir problemle en son ne zaman karşılaştın?
• Bir yapay zekâ ajanının yazdığı kodu kontrol etmek, kodu yazmaktan neden daha kolay olsun?

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