Algorytm pseudowielomianowy
Algorytm pseudowielomianowy to taki, którego złożoność obliczeniowa nie jest jedynie uzależniona od rozmiaru danych wejściowych, ale także od konkretnego parametru charakterystycznego dla danego problemu.
Na przykład, w przypadku problemu plecakowego istnieje algorytm pseudowielomianowy, który rozwiązuje ten problem w czasie
Θ(n ⋅ k)
, gdzie n oznacza rozmiar danych wejściowych, a k to rozmiar plecaka.
Ta forma złożoności jest mniej restrykcyjna niż w przypadku algorytmów wielomianowych, których czas działania jest ograniczony przez wielomian w odniesieniu do wielkości wejścia zapisanego w systemie binarnym (lub innym systemie pozycyjnym o podstawie większej od 1).
Jeżeli jakikolwiek problem, który jest silnie NP-zupełny, ma algorytm pseudowielomianowy, to każdy problem z klasy NP również można rozwiązać w czasie wielomianowym, co oznacza, że P = NP.
Problem plecakowy jest NP-trudny i nie ma znanego algorytmu wielomianowego dla tego problemu (gdyby taki algorytm istniał, oznaczałoby to, że P = NP). Jednak istnieje algorytm pseudowielomianowy oparty na programowaniu dynamicznym, który można zastosować do tego problemu.
