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

'''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).

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 ==

* [[cykl Hamiltona|problem cyklu Hamiltona]]

* [[problem komiwojażeraplecakowy|decyzyjna wersja problemu komiwojażeraplecakowego]] (COMI)

* [[problem spełnialnościkliki]] (SAT)

* [[problem trójkolorowalnościkomiwojażera|decyzyjna wersja problemu komiwojażera]] (3COLCOMI)