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

Dodane 9 bajtów ,  2 lata temu
m
(Udowodnienie NP-zupełność=P nie zepsułoby RSA, ponieważ faktoryzacja liczb jest problemem NP, nie NP-zupełnym. Komuś się pomyliła NP-zupełność z NP-trudnością.)
m (WP:SK+Bn)
 
'''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=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>.
 
== Przykłady ==
Przykłady problemów NP-zupełnych:
* [[cykl Hamiltona|problem cyklu Hamiltona]]
* [[cykliczne pokrycie krawędziowe]]
*[[problem kliki]]
* [[problem komiwojażeraplecakowy|decyzyjna wersja problemu komiwojażeraplecakowego]] (COMI)
* [[kolorowanie grafu]]
*[[problem pokrycia wierzchołkowego|pokrycie wierzchołkowe]]
* [[problem spełnialnościkliki]] (SAT)
* [[problem trójkolorowalnościkomiwojażera|decyzyjna wersja problemu komiwojażera]] (3COLCOMI)
* [[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 klikiNP-trudny]]
* [[problem obliczeniowy]]
* [[problem silnie NP-trudnyzupełny]]
 
{{klasy złożoności}}
 
== Przypisy ==
{{Przypisy}}