NP-Tamlık ve İndirgemeler
Bir NP-tam problem, NP sınıfındaki en zor problemlerden biri olarak kabul edilmektedir; zira her NP problemi ona verimli bir şekilde indirgenebilmekte, dolayısıyla herhangi bir NP-tam problemin hızlıca çözülmesi, tüm NP problemlerinin çözümünü mümkün kılmaktadır.
Tanım
Bir problem, NP içinde yer alması ve NP'deki her problemin polinom zamanlı bir indirgeme ile ona indirgenebilmesi durumunda NP-tam olarak tanımlanır; bu tür problemler, NP'nin maksimum zorluktaki üyeleri olup, verimli dönüşüme kadar birbirine eşdeğerdir.
Kapsam
Bu konu, polinom zamanda doğrulanabilir problemlerin NP sınıfını, polinom zamanlı çok-bir indirgemeleri, tatmin edilebilirliği NP-tam olarak belirleyen Cook–Levin teoremini, Karp'ın NP-tam kombinatoryal problemler kataloğunu ve bilinen problemlerden indirgeme yoluyla yeni problemlerin NP-tam olduğunu kanıtlama metodolojisini kapsamaktadır.
Temel sorular
- Bir problemin NP'deki en zor problemler arasında olması ne anlama gelmektedir?
- Cook–Levin teoremi, ilk NP-tam problemi nasıl belirlemektedir?
- İndirgemeler, yeni bir problemin NP-tam olduğunu kanıtlamak için nasıl kullanılmaktadır?
- Bir problemin NP-tamlığının binlerce başka problem için neden çıkarımları bulunmaktadır?
Temel kuramlar
- Cook–Levin teoremi
- Boole tatmin edilebilirliği NP-tamdır, çünkü herhangi bir polinom zamanlı doğrulayıcının hesaplaması bir tatmin edilebilirliği örneği olarak kodlanabilmekte ve bu durum, diğer problemlerin türetildiği temel tam problemi sağlamaktadır.
- Karp indirgemeleri ve NP-tam problemler ağı
- Karp, grafik renklendirmeden gezgin satıcı karar problemine kadar yirmi bir doğal problemin polinom zamanlı indirgemelerle NP-tam olduğunu göstermiş ve indirgemelerin büyüyen bir ağı aracılığıyla zorluk derecesini belirleme pratiğini başlatmıştır.
Klinik önem
NP-tamlık, çözülemezliğin pratik bir teşhisi olarak kabul edilmektedir: çizelgeleme, lojistik, tasarım veya doğrulama gibi alanlardaki bir problem NP-tam olarak gösterildiğinde, mühendisler garantili hızlı bir kesin algoritma arayışından vazgeçerek yaklaşık algoritmalara, sezgisellere, tam sayı programlama çözücülerine veya problemi çözülebilir kılan kısıtlamalara yönelmektedirler.
Tarihçe
Cook, 1971 yılında tatmin edilebilirliği NP-tam olarak kanıtlamış, Levin ise Sovyetler Birliği'nde bağımsız olarak eşdeğer sonuçlar elde etmiştir. 1972'de Karp, yirmi bir ek NP-tam problem göstererek bu olgunun yaygınlığını ortaya koymuş ve NP-tamlığı hesaplama zorluğunu teşhis etmek için merkezi bir araç haline getirmiştir.
Öne çıkan isimler
- Stephen Cook
- Leonid Levin
- Richard Karp
İlgili konular
Temel eserler
- cook1971
- karp1972
Sıkça sorulan sorular
- NP ne anlama gelmektedir?
- NP, nondeterministik polinom zaman anlamına gelmektedir. Eşdeğer olarak, bir problem, önerilen bir çözümün polinom zamanda kontrol edilebilmesi durumunda NP'dedir, çözümünü bulmak zor görünse bile. Belirli bir uzunluğun altındaki gezgin satıcı rotası, verildiğinde doğrulanması kolay ancak keşfedilmesi görünüşte zordur.
- Yeni bir problemin NP-tam olduğunu nasıl kanıtlarsınız?
- İki şeyi göstermeniz gerekmektedir: problemin NP içinde olduğunu, böylece aday çözümlerin hızlıca kontrol edilebilir olduğunu ve bilinen bir NP-tam problemin polinom zamanda ona indirgenebildiğini. Bu indirgeme, bilinen zorluğu aktararak yeni problemi NP'deki en zorlar arasına yerleştirmektedir.