P vs NP
Bir bulmacayı çözmek ile çözülmüş olduğunu doğrulamak arasında gerçek bir fark var mıdır? Sezgisel olarak "evet" dersiniz — ama kimse bunu kanıtlayamadı. Bu, bilgisayar biliminin kalbini durduracak sorudur.
Bir çözümü doğrulamak polinom zamanda mümkünse,
o çözümü bulmak da polinom zamanda mümkün müdür?
Şifreni doğrulamak kolaydır — bulmak mı?
Bir arkadaşınız size 1000 parçalık bir bulmacayı tamamlanmış hâlde gösterse, doğru çözüm olduğunu saniyeler içinde anlarsınız. Ama sıfırdan çözmek saatler sürebilir. İşte P vs NP'nin kalbi burada gizlidir.
Sudoku'nun çözümünü kontrol etmek kolaydır; bulmak zordur. RSA ile şifrelenmiş bir mesajı kırmak zordur; doğru anahtarı deneyin, hemen açılır. Doğrulama ile keşfetme arasında gerçek bir asimetri var mıdır — yoksa henüz zekice bir algoritma bulamadık mı?
- →Liste sıralama
- →En kısa yol (Dijkstra)
- →Matris çarpımı
- →Asal sayı kontrolü
- →Sudoku çözmek
- →Gezgin satıcı
- →Protein katlama
- →RSA şifre kırma
1971 — Cook'un devrimci kâğıdı
Stephen Cook, 1971'de Toronto Üniversitesi'nde "Teorem Kanıtlama Prosedürlerinin Karmaşıklığı" adlı makalesini yayımladı. Sıradan bir başlık, devrim niteliğinde bir içerik.
Cook, NP-tam kavramını ortaya attı: Eğer herhangi bir NP-tam problemi verimli çözülürse, tüm NP problemleri verimli çözülebilir. Leonid Levin aynı yıl Sovyetler'de bağımsız olarak aynı sonuca ulaştı. İki kıtada, birbirinden habersiz iki zihin aynı soruya takılmıştı.
"Eğer P = NP ise, matematikçilerin kanıt aramak için harcadıkları çabanın tümü otomatikleşebilir. Düşünce, hesaplamanın özel bir formu haline gelir."
— Scott Aaronson, Kuantum Hesaplama TeorisyeniP = NP olsaydı her şey değişirdi
Bu eşitlik kanıtlansaydı, insanlık tarihinin en büyük dönüşümü yaşanırdı:
Neden bu kadar zor?
Razborov ve Rudich 1994'te "doğallaştırma engelini" kanıtladı: Bilinen kanıt tekniklerinin büyük çoğunluğu yapısal olarak yetersiz. Sadece cevabı bilmiyoruz — doğru soruyu sormayı bile tam öğrenemedik.
2011'de Vinay Deolalikar 100 sayfalık bir "kanıt" yayımladı. Birkaç gün matematikçileri heyecanlandırdı. Sonra hatalar bulundu. Çoğu matematikçi P ≠ NP olduğuna inanır — ama inanmak kanıt değildir.
Düşünce ile hesaplama arasındaki sınır.
P vs NP yalnızca bir bilgisayar bilimi sorusu değil — zihnin sınırlarını sorgulayan felsefi bir meydan okumadır. Ve cevabı hâlâ boşlukta asılı durmaktadır.