Problem NP-zupełny: Różnice pomiędzy wersjami

[wersja przejrzana]

Usunięta treść Dodana treść

Jednokolumnowy

Aktualna wersja na dzień 11:17, 23 lut 2019

Problem NP-zupełny (NPC, ang. NP-Complete) – problem zupełny w klasie NP, ze względu na redukcje wielomianowe, to problem, który należy do klasy NP oraz dowolny problem należący do NP może być do niego zredukowany w czasie wielomianowym. Czasami zamiast redukcji w czasie wielomianowym używa się redukcji w pamięci logarytmicznej. Pytanie, czy są to definicje równoważne pozostaje pytaniem otwartym^[1]. Taka definicja problemów NP-zupełnych implikuje fakt, że jeśli tylko potrafimy rozwiązać jakikolwiek problem NP-zupełny w czasie wielomianowym, to potrafimy rozwiązać w takim czasie wszystkie problemy NP. Problemy NP-zupełne można więc traktować jako najtrudniejsze problemy klasy NP (z punktu widzenia wielomianowej rozwiązywalności).

Pierwszym problemem, którego NP-zupełność wykazano, był problem SAT, czyli problem spełnialności formuł zdaniowych. Udowodnił to w 1971 roku Stephen Cook.

Pytanie, czy problemy NP-zupełne można rozwiązywać w czasie wielomianowym, jest największą zagadką informatyki teoretycznej. Ciągle nie udowodniono tego, iż $P\neq NP$ (nie udowodniono także przeciwnie, że $P=NP$ ), która jednoznacznie stwierdzałaby, że jest to niemożliwe. Rozwiązanie tego problemu znalazło się na liście problemów milenijnych. Mimo ufundowania miliona dolarów za rozwiązanie tak postawionego problemu, nikomu się to nie udało.

Problem nie może być jednocześnie NP-zupełny i CoNP-zupełny, chyba że $NP=CoNP.$

Przykłady[edytuj | edytuj kod]

Przykłady problemów NP-zupełnych:

Zobacz też[edytuj | edytuj kod]

Przypisy[edytuj | edytuj kod]

↑ Christos H Papadimitriou: Złożoność obliczeniowa. Warszawa: Wydawnictwa Naukowo-Techniczne, 2002, s. 182, 192. ISBN 83-204-2659-6.

[1] Christos H Papadimitriou: Złożoność obliczeniowa. Warszawa: Wydawnictwa Naukowo-Techniczne, 2002, s. 182, 192. ISBN 83-204-2659-6.

[1]

@@ Linia 1: / Linia 1: @@
-'''Problem NP-zupełny''' ('''NPC''', {{Ang.|NP-Complete}}) – [[problem zupełny]] w klasie [[Problem NP|NP]], ze względu na redukcje wielomianowe, to problem, który należy do klasy NP oraz dowolny problem należący do NP może być do niego zredukowany w czasie wielomianowym. Czasami zamiast redukcji w czasie wielomianowym używa się redukcji w pamięci logarytmicznej. Pytanie, czy są to definicje równoważne pozostaje pytaniem otwartym<ref>{{cytuj książkę |nazwisko=Papadimitriou |imię=Christos H |tytuł=Złożoność obliczeniowa  | data=2002  |wydawca=Wydawnictwa Naukowo-Techniczne |miejsce=Warszawa |isbn = 83-204-2659-6 |strony = 182,192}}</ref>. Taka definicja problemów NP-zupełnych implikuje fakt, że jeśli tylko potrafimy rozwiązać jakikolwiek problem NP-zupełny w czasie wielomianowym, to potrafimy rozwiązać w takim czasie wszystkie problemy NP. Problemy NP-zupełne można więc traktować jako najtrudniejsze problemy klasy NP (z punktu widzenia wielomianowej rozwiązywalności).
+'''Problem NP-zupełny''' ('''NPC''', {{Ang.|NP-Complete}}) – [[problem zupełny]] w klasie [[Problem NP|NP]], ze względu na redukcje wielomianowe, to problem, który należy do klasy NP oraz dowolny problem należący do NP może być do niego zredukowany w czasie wielomianowym. Czasami zamiast redukcji w czasie wielomianowym używa się redukcji w pamięci logarytmicznej. Pytanie, czy są to definicje równoważne pozostaje pytaniem otwartym<ref>{{cytuj książkę |nazwisko=Papadimitriou |imię=Christos H |tytuł=Złożoność obliczeniowa |data=2002 |wydawca=Wydawnictwa Naukowo-Techniczne |miejsce=Warszawa |isbn = 83-204-2659-6 |strony = 182, 192}}</ref>. Taka definicja problemów NP-zupełnych implikuje fakt, że jeśli tylko potrafimy rozwiązać jakikolwiek problem NP-zupełny w czasie wielomianowym, to potrafimy rozwiązać w takim czasie wszystkie problemy NP. Problemy NP-zupełne można więc traktować jako najtrudniejsze problemy klasy NP (z punktu widzenia wielomianowej rozwiązywalności).
 Pierwszym problemem, którego NP-zupełność wykazano, był problem [[Problem spełnialności|SAT]], czyli problem spełnialności formuł zdaniowych. Udowodnił to w 1971 roku [[Stephen Cook]].
-Pytanie, czy problemy NP-zupełne można rozwiązywać w czasie wielomianowym, jest największą zagadką informatyki teoretycznej. Ciągle nie udowodniono tego, iż <math>P\not=NP</math> (nie udowodniono także przeciwnie, że <math>P=NP</math>), która jednoznacznie stwierdzałaby, że jest to niemożliwe. Rozwiązanie tego problemu znalazło się na liście [[problemy milenijne|problemów milenijnych]]. Mimo ufundowania miliona dolarów za rozwiązanie tak postawionego problemu, nikomu się to nie udało.
+Pytanie, czy problemy NP-zupełne można rozwiązywać w czasie wielomianowym, jest największą zagadką informatyki teoretycznej. Ciągle nie udowodniono tego, iż <math>P\neq NP</math> (nie udowodniono także przeciwnie, że <math>P=NP</math>), która jednoznacznie stwierdzałaby, że jest to niemożliwe. Rozwiązanie tego problemu znalazło się na liście [[problemy milenijne|problemów milenijnych]]. Mimo ufundowania miliona dolarów za rozwiązanie tak postawionego problemu, nikomu się to nie udało.
-Problem nie może być jednocześnie NP-zupełny i [[Klasa Co-NPC|CoNP-zupełny]], chyba że <math>NP=CoNP</math>.
+Problem nie może być jednocześnie NP-zupełny i [[Klasa Co-NPC|CoNP-zupełny]], chyba że <math>NP=CoNP.</math>
-==Przykłady==
+== Przykłady ==
 Przykłady problemów NP-zupełnych:
-*[[cykl Hamiltona|problem cyklu Hamiltona]]
+* [[cykl Hamiltona|problem cyklu Hamiltona]]
+* [[cykliczne pokrycie krawędziowe]]
-*[[problem kliki]]
-*[[problem komiwojażera|decyzyjna wersja problemu komiwojażera]] (COMI)
+* [[problem plecakowy|decyzyjna wersja problemu plecakowego]]
+* [[kolorowanie grafu]]
-*[[problem pokrycia wierzchołkowego|pokrycie wierzchołkowe]]
-*[[problem spełnialności]] (SAT)
+* [[problem kliki]]
-*[[problem trójkolorowalności]] (3COL)
+* [[problem komiwojażera|decyzyjna wersja problemu komiwojażera]] (COMI)
+* [[problem pokrycia wierzchołkowego|pokrycie wierzchołkowe]]
-*[[kolorowanie grafu]]
+* [[problem spełnialności]] (SAT)
-*[[cykliczne pokrycie krawędziowe]]
+* [[problem trójkolorowalności]] (3COL)
-*[[problem plecakowy|decyzyjna wersja problemu plecakowego]]
 == Zobacz też ==
-* [[problem NP-trudny]]
-* [[problem silnie NP-zupełny]]
 * [[lista problemów NP-zupełnych]]
 * [[problem NP-pośredni]]
+* [[problem NP-trudny]]
 * [[problem obliczeniowy]]
+* [[problem silnie NP-zupełny]]
 {{klasy złożoności}}
 == Przypisy ==
 {{Przypisy}}

Uważane za wykonalne	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL NL NC SC CC P (P-zupełność) ZPP RP BPP BQP APX
Podejrzewane o niewykonalność	UP NP NP-zupełność NP-trudność co-NP co-NP-zupełność AM QMA PH ⊕P PP #P (#P-zupełność) IP PSPACE (PSPACE-zupełność)
Uważane za niewykonalne	EXPTIME NEXPTIME EXPSPACE ELEMENTARY PR R RE ALL
Hierarchie klas	Hierarchia wielomianowa Hierarchia wykładnicza Hierarchia Grzegorczyka Hierarchia arytmetyczna Hierarchia Boole'owska
Rodziny klas	DTIME NTIME DSPACE NSPACE Dowód weryfikowalny probabilistycznie Interaktywny system dowodowy