NP-Tamlığı ve Çözülemezlik
NP-tamlığı, NP sınıfındaki en zor problemleri — yani her NP probleminin indirgenebildiği problemleri — tanımlamakta ve verimli bir algoritmanın bilinmediği veya olası görülmediği problemleri tanımak için standart bir çerçeve sunmaktadır.
Tanım
Bir karar problemi, NP içinde yer alıyorsa (evet-örnekleri verimli bir şekilde doğrulanabilir sertifikalara sahipse) ve NP'deki her problem polinom zamanda ona indirgenebiliyorsa NP-tamdır; bu tür problemler NP'deki en zor problemler olup, herhangi biri için polinom zamanlı bir algoritma, hepsi için bir algoritma sağlayacaktır.
Kapsam
Bu konu, P ve NP karmaşıklık sınıflarını, polinom zamanlı indirgemeleri, NP-zorluk ve NP-tamlığı tanımlarını, tatmin edilebilirliği NP-tam olarak belirleyen Cook-Levin teoremini, Karp'ın NP-tam problemler kataloğunu ve çözülemezliğin algoritma tasarımı üzerindeki pratik sonuçlarını kapsamaktadır. Bu kavramlar, zor problemlerin tanınması ve bunlarla başa çıkılmasına uygulanmaktadır; hesaplamalı karmaşıklık sınıflarının daha geniş resmi kuramı, hesaplama kuramı alt alanında ele alınmaktadır.
Temel sorular
- P ve NP karmaşıklık sınıflarını birbirinden ayıran nedir?
- Polinom zamanlı bir indirgeme, zorluğu bir problemden diğerine nasıl aktarır?
- Cook-Levin teoremi neyi ortaya koyar ve tatmin edilebilirlik neden merkezidir?
- Yeni bir problem, bilinen bir problemden indirgeme yoluyla nasıl NP-tam olarak kanıtlanır?
- Bir problem NP-zor olarak gösterildikten sonra hangi algoritmik stratejiler kalır?
Anahtar kavramlar
- P karmaşıklık sınıfı
- NP karmaşıklık sınıfı
- polinom zamanlı indirgeme
- NP-zorluk
- NP-tamlığı
- Cook-Levin teoremi
- Boole tatmin edilebilirliği (SAT)
- P'ye karşı NP sorunu
Temel kuramlar
- Cook-Levin teoremi
- Cook-Levin teoremi, Boole tatmin edilebilirliğinin (SAT) NP-tam olduğunu kanıtlamaktadır: NP'deki her problem polinom zamanda ona indirgenmekte, böylece ilk NP-tam problemi sağlamakta ve diğerlerinin zor olduğunu kanıtlamak için bir dayanak noktası oluşturmaktadır.
- Kombinatoryal problemler arasında indirgenebilirlik
- Karp, polinom zamanlı indirgemelerin birçok doğal problemi — klik, tepe örtüsü, Hamilton döngüsü, bölme ve diğerleri gibi — bir NP-tam problemler ağına bağladığını göstermiştir; böylece her birinin diğerinden indirgeme yoluyla zor olduğu kanıtlanabilmektedir.
Klinik önem
Bir problemin NP-tam olduğunu tanımak, bilişimdeki en pratik olarak faydalı sonuçlardan biri olarak kabul edilmektedir: bu durum, mühendislere hızlı ve kesin bir algoritma beklememelerini, bunun yerine yaklaşıklık algoritmaları, sezgisel yöntemler (heuristics), tipik durumlar için ayarlanmış kesin çözücüler veya çözülebilir özel durumlara kısıtlamalar kullanmalarını önermektedir. Birçok zamanlama, yönlendirme, paketleme ve tasarım problemi NP-tamdır.
Tarihçe
Stephen Cook, 1971'de NP-tamlığı tanıtmış ve SAT'ın NP-tam olduğunu kanıtlamıştır. Leonid Levin, benzer sonuçlara bağımsız olarak ulaşmıştır. Richard Karp'ın 1972 tarihli makalesi, 21 doğal problemin NP-tam olduğunu göstermiş ve bu çerçevenin kapsamını belirlemiştir. Garey ve Johnson'ın 1979 tarihli kitabı, yüzlerce NP-tam problemi kataloglamış ve standart bir referans haline gelmiştir.
Tartışmalar
- P'ye karşı NP
- P'nin NP'ye eşit olup olmadığı — yani verimli bir şekilde doğrulanabilen her problemin aynı zamanda verimli bir şekilde çözülebilir olup olmadığı — alanın en önemli açık problemidir; neredeyse tüm araştırmacılar P'nin NP'ye eşit olmadığını varsaymaktadır, ancak soru çözülememiş olup bir Milenyum Ödülü problemidir.
Öne çıkan isimler
- Stephen Cook
- Richard Karp
- Leonid Levin
- Michael Garey
- David Johnson
İlgili konular
Temel eserler
- cook1971
- karp1972
- cormen2009
Sıkça sorulan sorular
- NP-zor ve NP-tam arasındaki fark nedir?
- Bir problem, her NP problemi polinom zamanda ona indirgenebiliyorsa NP-zordur, ancak kendisinin NP içinde olması veya bir karar problemi olması gerekmez. Bir problem, hem NP-zor hem de NP içinde ise NP-tamdır. NP-tam problemler, hala NP içinde olan en zor problemlerdir.
- NP-tamlığı, bir problemin asla çözülemeyeceği anlamına mı gelir?
- Hayır. Bu, tüm girdiler için polinom zamanlı bir algoritmanın bilinmediği ve P'nin NP'ye eşit olmaması durumunda muhtemelen böyle bir algoritmanın var olmadığı anlamına gelmektedir. Pratikte bu tür problemler, yaklaşıklık algoritmaları, sezgisel yöntemler (heuristics), gerçekçi durumlar üzerinde çalışan üstel zamanlı çözücüler veya özel durumlara kısıtlama getirilerek ele alınmaktadır.