NP sertliği - NP-hardness

Daha nazik bir giriş için bkz. P'ye karşı NP sorunu.
P, NP, NP-tam ve NP-zor problemler için Euler diyagramı.
Euler diyagramı için P, NP, NP-tamamlandı ve NP-zor problemler. Sol taraf varsayımı altında geçerlidir P ≠ NP sağ taraf, P = NP varsayımı altında geçerlidir (boş dil ve onun tamamlayıcısının hiçbir zaman NP-tam olmaması dışında)

İçinde hesaplama karmaşıklığı teorisi, NP sertliği (deterministik olmayan polinom zaman sertlik) gayri resmi olarak "en az en zor problemler kadar zor olan bir problemler sınıfının tanımlayıcı özelliğidir. NP ". NP açısından zor bir soruna basit bir örnek, alt küme toplamı sorunu.

Daha kesin bir özellik ise: bir problem H her sorun olduğunda NP zordur L NP'de olabilir indirgenmiş içinde polinom zamanı -e H; yani, bir çözüm varsayarsak H 1 birim zaman alır, HÇözümü çözmek için kullanılabilir L polinom zamanda.[1][2] Sonuç olarak, herhangi bir NP-zor problemi çözmek için bir polinom zaman algoritması bulmak, NP'deki tüm problemler için polinom zaman algoritmaları verecektir. Şüphelenildiği gibi P NP, böyle bir algoritmanın mevcut olması olası değildir.[3]

Yaygın bir yanılgı, NP "NP-hard", "polinom olmayan" anlamına gelirken, aslında "kararsız polinom kabul edilebilir sorunlar ".[4] NP-zor problemler için polinom-zaman algoritmaları olmadığından şüpheleniliyor, ancak bu kanıtlanmadı.[5] Üstelik sınıf P tüm problemlerin polinom zamanda çözülebildiği, NP sınıf.[6]

Tanım

Bir karar problemi H her problem için NP zordur L NP'de bir polinom zamanlı çok bir indirgeme itibaren L -e H.[1]:80Eşdeğer bir tanım, her sorunun L NP'de çözülebilir polinom zamanı tarafından oracle makinesi bir oracle ile H.[7] Gayri resmi olarak, böyle bir oracle makinesini çözmek için bir alt program olarak çağıran bir algoritma düşünülebilir. H ve çözer L alt rutin çağrısı hesaplamak için yalnızca bir adım atarsa ​​polinom zamanında.

Başka bir tanım, bir polinom-zaman azalması olmasını gerektirmektir. NP tamamlandı sorun G -e H.[1]:91 Herhangi bir problem gibi L NP'de polinom zamanında azalır G, L sırayla azalır H polinom zamanda bu yeni tanım bir öncekini ifade eder. Garip bir şekilde, NP-zor sınıfını karar problemlerine sınırlamaz ve ayrıca şunları içerir: arama problemleri veya optimizasyon sorunları.

Sonuçlar

P ≠ NP ise, NP-zor problemler polinom zamanda çözülemez.

Bazı NP-zor optimizasyon problemleri polinom zamanlı olabilir yaklaşık sabit bir yaklaşım oranına kadar (özellikle, APX ) veya herhangi bir yaklaşım oranına kadar ( PTAS veya FPTAS ).

Örnekler

NP-zor bir soruna bir örnek karardır alt küme toplamı sorunu: bir tam sayı kümesi verildiğinde, bunların boş olmayan herhangi bir alt kümesinin toplamı sıfıra kadar mı? Bu bir karar problemi ve NP-tamamlanmış olur. NP-zor problemin başka bir örneği, ağırlıklı bir grafiğin tüm düğümleri boyunca en düşük maliyetli döngüsel rotayı bulmanın optimizasyon problemidir. Bu genellikle seyyar satıcı sorunu.[8]

Karar sorunları var NP-zor Ama değil NP tamamlandı benzeri durdurma sorunu. "Bir program ve girdisi verildiğinde sonsuza kadar çalışır mı?" Diye soran problem budur. Bu bir Evet/Hayır soru ve bu yüzden bir karar problemidir. Durdurma sorununun NP-zor olduğunu ancak NP-tam olmadığını kanıtlamak kolaydır. Örneğin, Boole karşılanabilirlik sorunu bir tanıma dönüştürülerek durdurma sorununa indirgenebilir Turing makinesi hepsini deneyen gerçek değer atamalar yapar ve formülü karşılayan birini bulduğunda durur, aksi takdirde sonsuz bir döngüye girer. Durma sorununun yerinde olmadığını görmek de kolaydır. NP NP'deki tüm problemler sınırlı sayıda operasyonda karar verilebildiğinden, ancak genel olarak durma problemi karar verilemez. Ayrıca NP-zor problemler de vardır. NP tamamlandı ne de Kararsız. Örneğin, dili gerçek ölçülü Boole formülleri karar verilebilir polinom uzay, ancak deterministik olmayan polinom zamanında değil (NP = PSPACE ).[9]

NP adlandırma kuralı

NP-zor problemler NP karmaşıklık sınıfının unsurları olmak zorunda değildir. NP merkezi bir rol oynadığından hesaplama karmaşıklığı, birkaç sınıfın temeli olarak kullanılır:

NP
Verilen hesaplamalı karar problemleri sınıfı Evet-çözünürlük, deterministik bir Turing makinesi (veya) ile polinom zamanda bir çözüm olarak doğrulanabilir. çözülebilir tarafından kararsız Polinom zamanda Turing makinesi).
NP-zor
En az NP'deki en zor problemler kadar zor problemler sınıfı. NP-zor problemler NP'nin unsurları olmak zorunda değildir; aslında, karar bile verilemeyebilirler.
NP tamamlandı
NP'deki en zor problemleri içeren karar problemleri sınıfı. Her NP-tam problem NP'de olmalıdır.
NP-kolay
En fazla NP kadar zor, ancak NP'de zorunlu değil.
NP eşdeğeri
Hem NP-zor hem de NP-kolay olan, ancak NP'de olması gerekmeyen karar problemleri.
NP-orta
P ve NP farklıysa, NP bölgesinde P ve NP-tam problemleri arasında kalan karar sorunları vardır. (Eğer P ve NP aynı sınıfsa, NP-ara problemler mevcut değildir çünkü bu durumda her NP-tam problem P'ye düşecektir ve tanım gereği NP'deki her problem bir NP-tam probleme indirgenebilir. )

Uygulama alanları

NP-zor sorunlar genellikle aşağıdaki alanlarda kural tabanlı dillerle ele alınır:

Referanslar

  1. ^ a b c Leeuwen, Jan van, ed. (1998). Teorik Bilgisayar Bilimi El Kitabı. Cilt A, Algoritmalar ve karmaşıklık. Amsterdam: Elsevier. ISBN  0262720140. OCLC  247934368.
  2. ^ Knuth Donald (1974). "NP-zor sorunlar hakkında son yazı". ACM SIGACT Haberleri. 6 (2): 15–16. doi:10.1145/1008304.1008305.
  3. ^ Daniel Pierre Bovet; Pierluigi Crescenzi (1994). Karmaşıklık Teorisine Giriş. Prentice Hall. s. 69. ISBN  0-13-915380-2.
  4. ^ "P ve NP". www.cs.uky.edu. Arşivlenen orijinal 2016-09-19 tarihinde. Alındı 2016-09-25.
  5. ^ "Shtetl İçin Optimize Edilmiş» Blog Arşivi »P ≠ NP için Bilimsel Örnek". www.scottaaronson.com. Alındı 2016-09-25.
  6. ^ "PHYS771 Ders 6: P, NP ve Arkadaşlar". www.scottaaronson.com. Alındı 2016-09-25.
  7. ^ V. J. Rayward-Smith (1986). Hesaplanabilirlikte İlk Kurs. Blackwell. s. 159. ISBN  0-632-01307-9.
  8. ^ Lawler, E.L.; Lenstra, J. K.; Rinnooy Kan, A. H. G .; Shmoys, D.B. (1985), Gezici Satıcı Sorunu: Kılavuzlu Kombinatoryal Optimizasyon Turu, John Wiley & Sons, ISBN  0-471-90413-9.
  9. ^ Daha doğrusu, bu dil PSPACE tamamlandı; örneğin bkz. Wegener, Ingo (2005), Karmaşıklık Teorisi: Etkili Algoritmaların Sınırlarını Keşfetmek, Springer, s. 189, ISBN  9783540210450.