Ocena brak

Jakiego rodzaju problemy tworzą klasę problemów NP – zupełnych? Podaj przykłady

Autor /Barnim7777 Dodano /29.12.2011

Klasę problemów NP – zupełnych tworzą problemy o następujących cechach:

- każdy taki problem da się w czasie wielomianowym przekształcić do innego

- dla wszystkich istnieją wątpliwe (wykładnicze) rozwiązania

- dla żadnego nie znaleziono rozsądnego (wielomianowego) rozwiązania

- dla żadnego nie udowodniono, że wymaga on czasu wykładniczego

- wszystkie te problemy są ze sobą powiązane (jeśli dla choćby jednego uda się znaleźć wielomianowe rozwiązanie to będzie wiadomo, że inne także da się rozwiązać w czasie wielomianowym i odwrotnie, jeśli wykaże się, że dla choćby jednego nie istnieje wielomianowe rozwiązanie, dla innych także go nie będzie)

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

- ścieżka Hamiltona

- ułożenia dwuwymiarowe (małpia układanka, wąż domino, figury geometryczne)

- problem komiwojażera

- załadunek plecaka

Do góry