Algorytm pseudowielomianowy

Ten artykuł od 2012-01 wymaga zweryfikowania podanych informacji. Należy podać wiarygodne źródła, najlepiej w formie przypisów bibliograficznych. Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte. Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

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 ${\displaystyle \Theta (n\cdot k)}$ , gdzie ${\displaystyle n}$ to rozmiar danych wejściowych, a ${\displaystyle 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