NP, NP-Complete və NP-Hard arasındakı fərqlər hansılardır?

NP , NP-CompleteNP-Hard arasındakı fərq nədir?

İnternette bir çox resurs bilirəm. Sizin şərhlərinizi oxumaq istərdim və səbəbi onlar orada və ya orada olanlardan fərqlənə bilər və mən bilmirəm.

785
07 дек. DarthVader dəsti 07 Dekabr 2009-12-07 04:11 '09 at 4:11 pm 2009-12-07 04:11
@ 10 cavab

Hesab edirəm ki, texniki təsəvvürlər başa düşmək üçün vaxt ayırdığından intuitiv təriflər axtarırsınız. Hər şeydən əvvəl, mən bu anlayışları başa düşmək üçün ilkin zəruri konsepsiyanı geri çağırıram.

  • Çətinliklə problem: Bəli və ya heç bir cavab ilə problem.

İndi biz bu mürəkkəblik siniflərini müəyyən edirik.

P

P, polinom zamanında həll oluna biləcək bütün həllər problemlərini əks etdirən mürəkkəblik sinifidir. Yəni, problemin nümunəsi nəzərə alınsa, polinom zamanında "yes" və ya "no" cavabı da həll edilə bilər.

Misal

G ilə əlaqəli grafiği nəzərə alsaq, kənarları heç bir kənarın monokromatik olmadığı üçün onun təpələri iki rənglə rənglənə bilərmi?

Alqoritm: Kefi bir verteksdən başlayın, qırmızı rəngə çəkin və bütün qonşuları mavi olur və davam edir. Bürcləri bitirdikdə dayandırın və ya bir kənar etmək məcburiyyətindəsiniz və hər iki son nöqtə eyni rəngdə olacaq.


NP

NP, cavabın bəli olduğu hallarda polinom zamanında təsdiq edilə biləcək bir sübuta sahib olan bütün həll problemlərinin bir qrupunu əks etdirən bir mürəkkəblik sinifidir.

Bu, kimsə bizə problemin surətini və bir sertifikatı (bəzən də şahid olaraq adlandırılır) verirsə, cavabı "bəli" verdiyimiz zaman polinomiyadakı düzgün olduğunu təsdiq edə bilərik.

Misal

Integer fərqləndirmə NP-dədir. Bu nm tamsayıları verən bir problemdir, 1 < f < m ilə bir tamsayı var, belə ki f ( f kiçik bir əmsal n ) bölür?

Bu bir həll problemidir, çünki cavablar bəli və ya yox. Kimsə bizə problemin bir surətini verərsə (buna görə bizə nm tamsayı verərlər) və 1 < f < m ilə bir tamsayı və f faktor n (sertifikat) olduğunu bildirirsə, cavabı polinomial vaxtda bölmə n / f .


NP-Komple

NP-Complete NP-də bütün məsələlərin X in toplanmasını əks etdirən bir mürəkkəblik sinfidir. Bunun üçün başqa bir problem NP Y polinomial dövrdə X ə endirilə bilər.

Səmimi olaraq, bu, tezliklə X həllini necə həll edəcəyimizi bilsək Y tez həll edə biləcəyimiz deməkdir. Xüsusilə, Y nümunələrinin x = f(y) -a çevrilməsi üçün polinomial vaxt alqoritmi f varsa, x = f(y) Y x = f(y) cavab verən əmlakla polinom zamanına daxil edilir f(y) -də bəli.

Misal

3-SAT . Bu, üç mövqedən birləşmə (OR) birləşməsi (AND) verildiyi bir problemdir, operatorları təşkil edir

 (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) 

burada hər bir x_vij bir Boolean dəyişən və ya sonlu bir əvvəlcədən təyin edilmiş siyahıdan (x_1, x_2, ... x_n) dəyişən bir dəyişiklikdir.

Hər bir NP probleminin 3-SAT-a düşə biləcəyini göstərmək olar. Bunun sübut edilməsi texniki cəhətdir və NP-nin texniki təsvirindən (qeyri-deterministik Turing maşınları əsasında) istifadə edilməsini tələb edir. Bu Cook teoremi kimi tanınır.

NP tam problemləri üçün vacibdir ki, onlardan birini həll etmək üçün deterministik polinomial vaxt alqoritmini tapa bilsəniz, onda hər NP problemi polinomial vaxtda həll oluna bilər (onları həll etmək üçün bir problem).


NP-hard

Səmimi olaraq, bunlar NP-kompleksi ilə bağlı problemlər kimi ən azı mürəkkəb problemlərdir. NP-çətin problemlərin NP-də olmadığı və problemləri həll etmək lazım olmadığına diqqət edin.

Burada dəqiq tərif, Y probleminin Y olduqda olmasıdır, belə ki Y yəni M polinomiyaya qədər azalır.

Hər hansı NP-tam problem polinomial dövrdə hər hansı digər NP-tam problemə endirildiyi üçün bütün NP-tam problemləri polinomiyadakı hər hansı bir NP-sərt problemə endirilə bilər. Daha sonra, polinom zamanında bir NP-sərt problemin həlli varsa, polinom zamanında bütün NP problemlərinə həll var.

Misal

Dayanacaq problemi NP problemidir. P problemi girildikdə və girişdə dayanarsam bu bir problemdir? Bu bir həll problemi, ancaq NP deyil. Hər hansı bir NP tam probleminin bu qədər azaldılacağı aydındır. Başqa bir nümunə olaraq, hər hansı bir NP tam NP-çətin problem.

Xoşladığım NP-tam problemi Mayın tarama gəmisi problemidir.


P = NP

Bu, kompüter elmində ən məşhur problemlərdən biridir və riyazi elmlərdə ən vacib suallardan biridir. Əslində, Clay İnstitutu bir problemi həll etmək üçün bir milyon dollar təklif edir (Stephen Kukun Clay saytında yazılması yaxşı bir fikirdir).

P aydındır ki, P NP-nin alt kəmiyyətidir. Açıq sual NP problemlərinin deterministik polinomial müvəqqəti həllərə malik olub-olmamasıdır. Əksəriyyəti inanmırlar. Sonuncu (və əhəmiyyətli) problemlə bağlı son məqalə P = NP: NP-ə qarşı problemin vəziyyəti P.

Bu mövzuda ən yaxşı kitab, Kompüter və Garey və Johnson tərəfindən pozulmazdır .

1021
07 дек. Cavab jason 07 dekabrda verilir. 2009-12-07 04:46 '09 at 04:46 am 2009-12-07 04:46

Ətrafa baxıram və uzun izahatları görürəm. Burada yekunlaşdırmaq üçün faydalı ola biləcək kiçik bir diaqramdır:

Üstündən aşağıya nə qədər mürəkkəbliyi artırdığına diqqət yetirin: hər hansı bir NP NP-Complete qədər azalda bilər və hər hansı bir NP-Complet tamamilə P (polinom) dövründə NP-Hard-ə endirilə bilər.

P-zamanda problemlərin daha mürəkkəb bir sinifini həll edərsəniz, bu, P-zamandakı bütün sadə problemləri necə həll etdiyini (məsələn, hər hansı NP-tam problemin P vaxtında).

 ____________________________________________________________ |  Problem növü |  P vaxtında doğrulanabilir  P vaxtında həll edilə bilər  Zorlukların artması ___________________________________________________________ |  | |  P |  Bəli  Bəli  | |  NP |  Bəli  Bəli və ya No * |  | |  NP-Komple |  Bəli  Unknown |  | |  NP-Hard |  Bəli və ya No **  Bilinməyən *** |  | ____________________________________________________________ V
border=0

Yes və ya Yazıdakı qeydlər:

  • P-də vaxtında həll oluna bilən problem NP.
  • NP-Complete olan NP-Hard problem P-time-da yoxlanılır.
  • *** NP-kompleks problemləri (bunların hamısı NP-nin alt hissəsini təşkil edir). NP qalan hissəsi çətindir.

Mən də bu cədvəlin çox faydalı olduğunu gördüm, bütün bu növlərin bir-birinə necə uyğun olduğunu görür (chartın sol yarısına daha çox diqqət yetirin).

180
22 окт. Johnson Wong cavab verdi 22 oct. 2013-10-22 09:08 '13 at 9:08 2013-10-22 09:08

Bu soruşulan suallara çox rəsmi cavabdır.

3233-dən 1 ədəddən çox olan iki ədəd məhsul kimi yazılacaqmı? Königsberg'in yeddi körpüsünün ətrafında iki dəfə körpü etmədən yol açmaq üçün bir yol varmı? Bunlar ortaq xarakterli suallara nümunədir. Cavabın effektiv şəkildə necə təyin ediləcəyi hələ dəqiq deyil, amma cavab bəli, yəni sübutları yoxlamaq üçün qısa və tezdir. Birinci halda, qeyri-inteqral faktorizasiya 51; ikincidə - körpülərdən keçmək üçün marşrut (məhdudiyyətlər qoymaq).

Problemin həlli yalnız bir parametrdə fərqli olan "bəli" və ya "yox" cavabı ilə bağlı bir sıra suallardır. Problemi COMPOSITE = {"Kompozit mi": n tamsayıdırsa, ya da EULERPATH = {" G Euler yolu varmı?": G sonlu bir grafiktir} deyirik.

İndi bəzi həllər problemləri özləri üçün səmərəli, həqiqi olmasa, alqoritmlər verir. 250 ildən çox əvvəl Euler Königsberq Yeddi Körpü kimi problemlər üçün səmərəli bir alqoritm aşkar etmişdir.

Digər tərəfdən, bir çox problemlər üçün həll yolları necə cavab ala bilməyəcəkdir, amma bəzi əlavə məlumatları bilsəniz, düzgün cavab verdiyinizi sübut etmək lazımdır. COMPOSITE bu kimi görünür: Sınaq bölünməsi açıq bir alqoritmdir və yavaş: 10 haneli bir ədədi çarpdırmaq üçün 100.000 mümkün divisor kimi bir şey sınamalısınız. Lakin, məsələn, kimsə sizə deyir ki, 61 61-ci bölmədirsə, sadə uzun bir bölmə doğru olduğundan əmin olmaq üçün effektiv bir vasitədir.

NP mürəkkəbliyi sinfi "evet" cavablarının qısa olduğu, sübutları tez bir zamanda təsdiqləyən bir həll problemləri klassıdır. COMPOSITE kimi. Əhəmiyyətli olan nöqtə bu tərifin problemin nə qədər kompleks olduğu haqqında bir şey söyləməməsidir. Bir problemi həll etmək üçün doğru və effektiv bir yolunuz varsa, kifayət qədər inandırıcı bir həlldə olan addımları yazın.

Alqoritm tədqiqatları davam edir və bütün yeni ağıllı alqoritmlər daim yaradılır. Bu gün səmərəli şəkildə necə həll ediləcəyinizi bilməyəcəyiniz bir problem sabah təsirli ola bilər (əgər varsa). Əslində, tədqiqatçılar 2002 - ci ilə qədər KOMPOSİT üçün təsirli bir həll tapmaq üçün araşdırdılar! Bütün bu nailiyyətləri ilə, həqiqətən, özünüzü soruşmalısınız: qısa dəlilləri yalnız bir illüziyanın olması haqqında həqiqətən azdırmı? Yəqin ki, effektiv sübutlara özünü verən hər hansı bir həllin həlli effektiv bir həlldir? Heç kim bilmir .

Bəlkə də, bu sahəyə ən böyük töhfə NP problemlərinin unikal sinifinin aşkar olunmasıdır. Hesablama sxemləri ilə oynandıqdan sonra Stephen Kuk, NP müxtəlifliyi probleminə həll tapdı və bu, digər NP problemindən daha çətin və ya daha çətin idi. Bu məsələyə effektiv bir həll NP-də hər hansı digər problemə effektiv bir həll yaratmaq üçün istifadə edilə bilər. Qısa bir müddət sonra, Richard Karp bir sıra digər həll problemlərinin eyni məqsədlə xidmət edə biləcəyini göstərdi. Bu problemlər, bir mənada, NP- də "ən çətin" problemlər NP-tam problemlər kimi tanındı.

Əlbəttə ki, NP yalnız həll problemləri bir sinifdir. Bir çox problem təbii olaraq aşağıdakı şəkildə tərtib edilmir: "N faktoru tapın", "hər bir vertexə gedən G sütununda ən qısa yol tapın", "növbəti mantıksal ifadəni gerçəkləşdirən bir sıra dəyişənlər verin". "NP" kimi bir sıra problemlər barədə rəsmi olaraq danışmaq mümkün olsa da, texniki cəhətdən çox mənalı deyil - onlar həll problemləri deyil. Bu problemlərin bəziləri NP tam problemi ilə eyni gücə malik ola bilər: bu problemləri effektiv həll etmək (həll etmədən) hər hansı bir NP probleminə təsirli həll yoluna gətirib çıxaracaqdır. Bu problem NP-hard adlanır.

68
07 дек. Cavab verdi Managu 07 Dekabr 2009-12-07 05:42 '09 da 5:42 'də 2009-12-07 05:42

Digər əla cavablara əlavə olaraq, NP, NP-Complete və NP-Hard arasında fərqləri göstərmək üçün insanlar tərəfindən istifadə edilən tipik bir nümunədir :

2019

38
24 нояб. Franck Dernoncourt tərəfindən verilmiş cavab 24 noyabr 2014-11-24 20:50 '14 saat 20:50 'də 2014-11-24 20:50

P v. NP və belə texniki mövzularda müzakirə edilmədən, "mətlə ilə problemləri" "birdən çox seçim ilə problemlər" ilə müqayisə etməkdir.

"Mətn problemini" həll etməyə çalışdığınız zaman, sıfırdan bir həll tapmaq lazımdır. Bir neçə seçimi ilə bir problemi həll etməyə çalışdığınız zaman seçiminiz var: ya "mətn problemi" kimi həll edin və ya sizə verilən hər bir cavabı əlaqələndirin və müvafiq namizədin cavabı seçin.

Tez-tez olur ki, "çox seçim problemi" müvafiq "söz problemi" dan daha sadədir: namizəd cavablarını əvəz etmək və uyğun olduqlarını yoxlamaq sıfırdan düzgün cavab tapmaqdan daha az səy tələb edə bilər.

İndi, polinom vaxtını "asan" edən səylə razılaşdığımız halda, P sinfi "sadə şifahi problemlərdən" ibarətdir və NP klubu "sadə seçilmiş vəzifələrdən" ibarət olacaq.

P v. NP: "Sözlərin problemləri kimi asan olmayan bir çox seçim ilə sadə problemlər varmı?" Yəni, bu cavabın doğruluğunu yoxlamaq üçün asan olan hər hansı bir problem varmı, lakin cavabı sıfırdan tapmaq çətindir?

İndi NP-nin nə olduğunu başa düşdüyümüz zaman intuisiyaya meydan vermək lazımdır. Görünür, "birdən çox seçim problemi" var ki, bu da bir mənada ən çətin haldır: əgər bu "ən çətin" problemlərdən birinə bir həll taparsan, NP ilə ALL Problemlər üçün bir həll tapa bilərik! Bik 40 il əvvəl kəşf etdikdə tam bir sürpriz oldu. Bu "ən çətin" problemlər NP-hard kimi tanınır. Onlardan birinə "mətn problemi həll" taparsanız, hər bir "sadə çox seçim" problemi üçün avtomatik olaraq "söz problemi həll" tapacaqsınız!

Nəhayət, NP-tam problemlər NP və NP-çətin problemlərdir. Bizim analojikliyimizdən sonra onlar eyni zamanda "çox seçimli problemlər" və "ən çətin məsələlər - mətlə ilə bağlı problemlər kimi asandır".

36
08 авг. Cavab Michael 08 aug verilir . 2013-08-08 23:41 '13 at 11:41 pm 2013-08-08 23:41

P (Polinomiya vaxtı): Adı özü təklif etdiyi kimi, bu, polinom zamanında həll oluna biləcək problemlərdir.

NP (Nondeterministik Polinomiya vaxtı): Bunlar polinom zamanında test edilə biləcək həll problemləri. Demək olar ki, müəyyən bir problemin həlli üçün çox vaxt polinomial həll olduğunu söyləyərəm, onu sübut etmək istəməyəm. Sonra polinom zamanında asanlıqla yoxlaya biləcəyiniz bir sübut verəcəyəm. Belə problemlər NP problemləri adlanır. Burada bu problem üçün çoxsaylı bir müvəqqəti həll olub-olmadığı barədə danışmırıq. Amma biz bu problemin polinom zamanında həllini yoxlamaqdan danışırıq.

NP-Hard: bu NP-də ən çətin problemlər kimi ən az çətindir. Polinom zamanında bu problemləri həll edərsə, mövcud ola biləcək hər hansı NP problemini həll edə bilərik. Xahiş edirik bu problemlərin mütləq NP problemləri olmadığını unutmayın. Bu, polinomiyadakı bu problemlərin həllini doğrulayamayacağımızın / mümkün olmadığını bildirir.

NP-Complete: Bunlar NP və NP-Hard olan problemlərdir. Bu, bu problemləri həll edə bilsək, başqa NP problemini həll edə bilərik və bu problemlərə həll yolları polinomial vaxtda yoxlanıla bilər.

26
04 окт. Nagakishore Sidde 04 oct tərəfindən verilmiş cavab . 2013-10-04 06:50 '13 'da 6:50' da 2013-10-04 06:50

Hesab edirəm ki, biz ona daha çox cavab verə bilərik. Mən bu suala cavab verdim və cavabımı oradan kopyaladım.

Ancaq ilk növbədə, NP problemi problemdir, bunun üçün bir çox vaxtın polinom həlli olduğunu sübut edə bilmərik. Müəyyən bir "problem-P" nin NP-sərtliyi, adətən, sübut edilmiş bir NP-çətin problemini polinomial zamanda "problem-P" halına gətirməklə sübut edir.

Qalan suallara cavab vermək üçün ilk növbədə NP-çətin problemlərin də NP-ləğvini başa düşməlisiniz. Bir NP-çətin problem NP-yə aiddirsə, NP tamdır. NP-yə aid olmaq üçün problem olmalıdır

(i) problemlərin həlli,
(ii) problemin həlli sayı sonlu olmalıdır və hər bir həll bir polinom uzunluğuna malik olmalıdır və (iii) bir polinom uzunluğunun həlli nəzərə alınarsa, problemin cavabı bəli / yox

NP-lərlə əlaqəli olmayan bir çox NP problemi ola biləcəyini görmək çətindir və onlar həll etmək daha çətindir. Bir intuitiv nümunə olaraq, faktiki cədvəlləri tapmaq üçün lazım olan səyahət edəni optimallaşdırma versiyası, uzunluğu <= k ilə bir cədvəlin olmadığını müəyyən etmək üçün lazım olan səyahət edən həlli versiyasından daha mürəkkəbdir.

16
18 июня '11 в 19:52 2011-06-18 19:52 Cavab Sushant Sharma tərəfindən 18 İyun, '11 'də 19:52 2011-06-18 19:52' də verilir

NP tam problemləri NP-Hard və NP mürəkkəblik sinifindədir. Buna görə də, hər hansı bir tapşırığın NP tam olduğunu göstərmək üçün problemin NP və NP-də çətin olduğunu göstərməlisiniz.

NP mürəkkəblik sinifində olan problemlər polinomial vaxtda qeyri-deterministik həll oluna bilər və NP-də bir problem üçün mümkün bir həll (məsələn, sertifikat) polinomial vaxtda düzgünlük üçün yoxlanıla bilər.

K-klik probleminə qeyri-deterministik bir həll nümunəsi bir şey ola bilər:

1) təsadüfi olaraq grafikdən k nodes seçin

2) bu k-qovşaqlarının bir klik yaratdığından əmin olun.

Yuxarıda göstərilən strategiya giriş grafiğinin ölçüsündə polinomdur və buna görə də k-klik problemi NP-dədir.

Polinom zamanında deterministik həll ediləcək bütün problemlərin NP-də olduğunu nəzərə alsaq.

Bir NP-çətin problemin ümumiyyətlə bir neçə NP-çətin problemdən probleminizə bir polinom vaxt göstəricisindən istifadə etdiyini göstərmək: http://en.wikipedia.org/wiki/Reduction_ ( komplekslik )

15
07 дек. Cavab awesomo 07 dek verilir . 2009-12-07 04:45 '09 saat 04:45 'da 2009-12-07 04:45

Bu sualın həqiqətən yaxşı cavabları var, buna görə öz izahınızı yazmaq mənasızdır. Buna görə hesablama mürəkkəbliyinin müxtəlif sinifləri haqqında böyük bir qaynaqla iştirak etməyə çalışacağam.

Hesablama mürəkkəbliyi yalnız P və NP olduğuna inananlar üçün hesablama kompleksliyi məsələləri ilə bağlı ən geniş resursdur . EP tərəfindən qoyulan problemlərə əlavə olaraq, bu, gözəl təsvirlər ilə yanaşı, təxminən 500 müxtəlif hesablama problemləri sinfini və sinfi təsvir edən fundamental tədqiqat sənədlərinin siyahısını əks etdirir.

5
14 янв. Cavab Salvador Dali 14 yanvar tərəfindən verilir . 2014-01-14 04:56 '14 'da 4:56 2014-01-14 04:56

Bunu başa düşdüyüm kimi, np-problemi problemdən daha çətin deyil. Əslində, tərifə görə, hər bir np-tam tapşırıq:

  • NP-də
  • np-hard

2019

3
13 авг. Cavab MrDrews 13 aug verilir . 2014-08-13 16:57 '14 'da 16:57 2014-08-13 16:57

etiketləri haqqında digər suallar və ya sual