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
Przykłady Przykłady problemów NP-zupełnych: problem cyklu Hamiltona cykliczne pokrycie krawędziowe decyzyjna wersja problemu plecakowego kolorowanie grafu problem kliki decyzyjna wersja problemu komiwojażera (COMI) pokrycie wierzchołkowe problem spełnialności (SAT) problem trójkolorowalności (3COL)
Zobacz też lista problemów NP-zupełnych problem NP-pośredni problem NP-trudny problem obliczeniowy problem silnie NP-zupełny
Przypisy
Kategoria:Klasy złożoności