Ne arasındaki farklarNP,NP-CompleteveNP-Zor?

İnternette pek çok kaynak farkındayım. Açıklamaları okumak istiyorum, ve bu nedenle orada ne o zaman farklı olabilir, ya da var ve ben farkında değilim.

Ben teknik tanımları anlamak için oldukça uzun bir süre gerektirir beri sezgisel tanımlar arıyorsun, öyle varsayalım. Öncelikle, hadi o tanımları anlamak için ilk gerekli bir kavram hatırlıyorum.

• Karar sorun: Bir sorunEvetyahayırcevap.

Şimdi, bize bu tanımlayalımkarmaşıklık sınıfları.

P

P polinom zamanda çözülebilen karar problemlerini kümesini temsil eden bir karmaşıklık sınıfıdır. Bu sorun bir örneğini vermiş, cevabı evet ya da hayır polinom zamanında karar verilebilir.

Örnek

Bir grafik G, köşeleri renkli hayır edge LED yani bu iki rengi kullanarak olabilir? bağlı verilen

Algoritma: kırmızı ve komşusu mavi renk rasgele bir tepe noktası ile başlayın ve devam edin. Köşe tükendiğinde durdurmak veya bitiş her ikisi de aynı renk olması bir kenarına yapmak zorunda kalıyor.

NP

NP için hangi örnekleri cevabı "evet" polinom zamanda doğrulanabilir deliller var. tüm kararı sorunlar kümesi temsil eden bir karmaşıklık sınıfıdır

Bu eğer birisi bize sorun, bir örnek ve bir sertifika (bazen bir tanık olarak da adlandırılır) cevabı evet olmak için verirse, doğru olduğunu polinom zamanda kontrol edebileceğimiz anlamına gelir.

Örnek

Tamsayı çarpanlaraolur NP. Bu sorun göz önüne alındığında tamsayılar n m, orada bir tam sayı f 1 < f < m böyle f böler n (f küçük bir faktör n)?

Bu cevapları evet ya da hayır, çünkü karar bir sorundur. Eğer birisi eller bize bir örnek problem (yani onlar bize el tamsayılar n m) ve bir tamsayı f 1 < f < m ve iddia f faktör n (sertifika), buluruz cevabıpolinom zamanbölümü n / f yaparak.

NP-Complete

NP için polinom zamanda X 18* *başka bir NP problemi azaltmak için mümkün olan tüm sorunlar kümesi X temsil karmaşıklık sınıfıdır.

Sezgisel olarak, eğer X hızlı bir şekilde çözmek için nasıl biliyorsanız Y hızlı bir şekilde çözebiliriz anlamına gelir bu. Doğrusu Y indirgenebilir X, yoksa bir polinom zaman algoritması f dönüşüm örnekleri y Y örnekleri x = f(y) X polinom zaman, özelliği olan cevap y Evet, Eğer ve sadece eğer cevap f(y) Evet.

Örnek

3-SAT. Bu bir bağlaç (Lar) 3-yan disjunctions (ORs), formun tabloların verilmiştir neyin sorunudur

(x_v11 OR x_v21 OR x_v31) AND 
(x_v12 OR x_v22 OR x_v32) AND 
...                       AND 
(x_v1n OR x_v2n OR x_v3n)

x_vij boolean bir değişken ya da sonlu önceden tanımlanmış bir listeden bir değişken azaltma (x_1, x_2, ... x_n) her yerde.

Gösterilebilirher NP sorun 3-SAT azaltılabilir. Bunun kanıtı da teknik ve NP teknik tanımının kullanılması gerekir (non-deterministik Turing makinaları dayalı). Bu olarak bilinirYemek teoremi.

Ne yapar NP-tam problemler önemli bir deterministik polinom zaman algoritması bulunabilir çözmek için bir tane, her NP sorun çözülebilir polinom zaman (bir sorun için kural hepsini).

NP-zor

Sezgisel olarak, bu sorunlar vardırNP-tam problemleri daha zor hatta. NP-zor problemler olduğunu unutmayınNP olmak zorunda değilvekarar problemleri olmak zorunda değilsiniz.

Kesin bir tanım işteX eğer NP-tam bir sorundur varsa NP-zor bir problem Y Y, polinom zamanda X indirgenebilir.

Ama NP-tam herhangi bir sorun polinom zamanda NP-tam başka bir sorun azaltılabilir beri, NP-tam, bütün problemleri polinom zamanda NP-hard herhangi bir sorun azaltılabilir. Eğer polinom zamanda NP-zor bir problem için bir çözüm varsa, polinom zamanda tüm NP sorunlar için bir çözüm var.

Örnek

durdurma sorunuklasik NP-zor bir sorundur. Bu program P giriş I will durdurmak verilen sorun bu mu? Bu karar bir sorundur ama NP değil. NP-tam herhangi bir sorun buna azaltılabilir açıktır.

NP-tam sevdiğim sorunu Minesweeper problem.

P = NP

Bilgisayar biliminin en ünlü ve matematiksel Bilimler alanında göze çarpan en önemli sorulardan biri bu. Aslında, Clay Institute sorun (Stephen Cook Clay web sitesi oldukça iyidir writeup) çözüm için bir milyon dolar teklif ediyor.

P, NP, alt açık. Açık soru ya da sorunları var NP deterministik polinom zamanda çözüm değildir. Büyük ölçüde yok olduğuna inanılmaktadır. Burada son kalan son bir makale (ve önemi) P = NP problemi: The Status of the P versus NP problem.

Bu konuda en iyi kitap Garey ve Johnson tarafından Computers and Intractability.