P ile NP Problemi
P ile NP problemi, çözümleri hızlı bir şekilde doğrulanabilen her problemin hızlı bir şekilde çözülüp çözülemeyeceğini sorgulayan, teorik bilgisayar biliminin merkezi açık sorusu ve Clay Millennium Ödülü problemlerinden biridir.
Tanım
P, polinom zamanda çözülebilen problemler sınıfı, NP ise önerilen çözümleri polinom zamanda doğrulanabilen problemler sınıfıdır; P ile NP problemi, bu iki sınıfın eşit olup olmadığını sorgulamaktadır ki bu, ancak ve ancak bazı NP-tam problemlerin polinom zamanda çözülebilmesi durumunda geçerlidir.
Kapsam
Bu konu, P ile NP'nin resmi ifadesini, herhangi bir NP-tam probleminin polinom zamanlı bir algoritmaya sahip olup olmadığına olan denkliğini, her iki cevabın sonuçlarını, ilerlemeyi engelleyen rölativizasyon (relativization), doğal kanıtlar (natural proofs) ve cebirleştirme (algebrization) gibi engelleri ve sınıfların farklı olduğuna dair yaygın varsayımı kapsamaktadır.
Temel sorular
- Bir çözüm bulmak, onu kontrol etmekten temel olarak daha mı zordur?
- Cevap neden herhangi tek bir NP-tam probleminin P içinde olup olmadığına bağlıdır?
- P, NP'ye eşit olsaydı dünya nasıl görünürdü ve eşit olmasaydı nasıl görünürdü?
- Onlarca yıllık çaba neden bu sorunu çözmekte başarısız olmuştur?
Temel kuramlar
- NP-tamlığa Denkliği
- P, NP'ye ancak ve ancak herhangi bir NP-tam probleminin polinom zamanlı bir algoritmaya sahip olması durumunda eşittir, bu nedenle kapsamlı soru, tatmin edilebilirlik (satisfiability) gibi tek bir somut problemin çözülebilirliğine indirgenmektedir.
- Kanıt Engelleri
- Rölativizasyon (relativization), doğal kanıtlar (natural proofs) ve cebirleştirme (algebrization) sonuçları, bilinen başlıca kanıt tekniklerinin P ile NP problemini çözemediğini göstermekte, bu da zorluğu açıklamakta ve temelden yeni yöntemler arayışına rehberlik etmektedir.
Klinik önem
P ve NP'nin varsayılan eşitsizliği, NP-zor problemlerin çözülemez olarak kabul edilmesinin ve kriptografinin güvenliğinin arkasındaki temel varsayımdır, zira NP problemlerinin verimli bir şekilde çözülmesi yaygın olarak kullanılan şifrelemeyi kıracaktır; P'nin NP'ye eşit olduğuna dair yapıcı bir kanıt, optimizasyon, lojistik ve bilimi dönüştürecektir.
Tarihçe
Cook, soruyu 1971'de NP-tamlık (NP-completeness) ile birlikte ortaya koymuş ve soru hızla temel bir problem olarak kabul edilmiştir. 1980'lerde devre alt sınırları (circuit lower bounds) aracılığıyla yapılan girişimler, Razborov ve Rudich tarafından tanımlanan doğal kanıtlar (natural proofs) engeliyle karşılaşmıştır ve 2000 yılında Clay Matematik Enstitüsü, bu problemi bir milyon dolarlık ödülle Milenyum Ödülü problemi olarak adlandırmıştır.
Tartışmalar
- P ile NP problemi hiç çözülebilecek mi ve cevabı nedir?
- Çoğu araştırmacı P'nin NP'ye eşit olmadığını varsaymaktadır, ancak henüz bir kanıt bulunmamaktadır ve bilinen tekniklerin yetersiz olduğu kanıtlanmıştır. Çözümün yakın olup olmadığı, radikal yeni matematik gerektirip gerektirmediği veya sorunun standart aksiyomlardan bile bağımsız olup olamayacağı konusunda görüşler farklılık göstermektedir.
Öne çıkan isimler
- Stephen Cook
- Leonid Levin
- Richard Karp
- Alexander Razborov
İlgili konular
Temel eserler
- cook1971
- aroraBarak2009
Sıkça sorulan sorular
- P, NP'ye eşit olsaydı ne olurdu?
- Optimal zamanlamadan kriptografik kodları kırmaya kadar şu anda çözülemez olduğuna inanılan birçok problem için verimli algoritmalar bulunurdu ve çözüm bulma eylemi, onları kontrol etmekten daha zor olmazdı. Ticaret, güvenlik ve bilim üzerindeki etkileri derin olurdu; çoğu uzmanın P'nin NP'ye eşit olmamasını beklemesinin nedenlerinden biri de budur.
- Bu problem neden bu kadar zor çözülmektedir?
- P'nin NP'ye eşit olduğunu kanıtlamak, kimsenin bulamadığı bir NP-tam problemi için hızlı bir algoritma gerektirmektedir; farklı olduklarını kanıtlamak ise böyle bir algoritmanın var olamayacağını göstermeyi gerektirir. Rölativizasyon (relativization) ve doğal kanıtlar (natural proofs) üzerine yapılan çalışmalar, standart tekniklerin ikincisini kanıtlamada doğası gereği yetersiz olduğunu göstermektedir, bu nedenle gerçekten yeni bir yaklaşıma ihtiyaç duyulmaktadır.