Algorytm pseudowielomianowy

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

Zobacz teżEdytuj