Algorytm pseudowielomianowy

Algorytm pseudowielomianowy – algorytm, którego złożoność obliczeniowa jest pseudowielomianowa. Oznacza to, że zależy ona nie tylko od rozmiaru danych wejściowych, ale również od pewnego parametru charakterystycznego dla danego problemu.

Przykładowo dla problemu plecakowego istnieje algorytm pseudowielomianowy który go rozwiązuje w czasie $\mathrm{\Theta }(n\cdot k)$ , gdzie $n$ to rozmiar danych wejściowych, a $k$ to rozmiar plecaka.

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, że P = NP). Znany jest jednak algorytm pseudowielomianowy dla tego problemu oparty na programowaniu dynamicznym.

Zobacz też

• problem liczbowy