Algorytm pseudowielomianowy

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.