Algorytm pseudowielomianowy
Z Wikipedii
Algorytm pseudowielomianowy to algorytm, którego czas działania jest ograniczony przez wielomian od wielkości wejścia, przy założeniu, że wejście jest zapisane w sposób unarny. Równoważnie: jest to algorytm, którego czas działania jest ograniczony przez wielomian od wielkości wejścia i maksymalnej wartości liczbowej występującej w opisie problemu.
Jest to słabsze założenie co do czasu działania niż założenie dla algorytmów wielomianowych, których czas działania jest ograniczony przez wielomian od wielkości wejścia zapisanego w systemie binarnym (lub innym systemie pozycyjnym o podstawie większej od 1).
Jeśli jakikolwiek problem silnie NP-zupełny ma algorytm pseudowielomianowy to, każdy problem z klasy NP da się rozwiązać w czasie wielomianowym, tzn P=NP.
Problem plecakowy jest NP-trudny i nie jest dla niego znany algorytm wielomianowy. (gdyby istniał oznaczałoby to, ze P=NP). Znany jest jednak algorytm pseudowielomianowy dla tego problemu, oparty na programowaniu dynamicznym.
