Problem NP-zupełny

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Problem NP-zupełny (NPC) czyli 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 czasie wielomianowym 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\not=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 problemu, nikomu się to nie udało.

Pytanie związane z problemami NP-zupełnymi ma szczególne znaczenie w kryptografii - rozwiązanie któregokolwiek problemu NP-zupełnego w czasie wielomianowym (a zatem rozwiązanie ich wszystkich) umożliwiłoby między innymi szybkie łamanie szyfru RSA (jednego z najbardziej popularnych szyfrów aktualnie stosowanych) - opiera się on na założeniu, że problem podziału dowolnej liczby na czynniki pierwsze nie jest problemem wielomianowym. Problem ten jest w NP, ale nie udowodniono jego NP-trudności.

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:

Przypisy

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

Zobacz też[edytuj | edytuj kod]