В теорията на изчислителната сложност, намаляването на полиномното време е метод за решаване на един проблем с помощта на друг. Редукциите с полиномно време често се използват в теорията на сложността за дефиниране както на класове на сложност, така и на пълни проблеми за тези класове. …
Какво се счита за полиномиално време?
За един алгоритъм се казва, че е с полиномиално време, ако времето му за изпълнение е горно ограничено от полиномен израз в размера на входа за алгоритъма, тоест T(n)=O(nk) за някаква положителна константа k.
Как да разберете дали нещо е полиномно време?
3 отговора. Алгоритъмът е полиномиален (има полиномно време на работа), ако за някое k, C>0, времето му на работа на входове с размер n е най-много Cnk. Еквивалентно, алгоритъмът е полином, ако за някакъв k>0 времето му на работа на входове с размер n е O(nk).
Какво се случва, ако намаляването е разрешено в експоненциално време?
Ако намаляването е разрешено експоненциално време, тогава то може напълно да реши първоначалния проблем и да създаде тривиален екземпляр на целевия проблем Това означава, че всеки проблем в NP е сведен до всеки друг проблем от такъв тип редукции, така че всеки проблем в NP е NP-завършен за експоненциално намаляване на времето.
Какво е експоненциален алгоритъм?
За един алгоритъм се казва, че е експоненциално време, ако T(n) е горна граница с 2poly( ) , където poly(n) е някакъв полином от n. По-формално, алгоритъмът е експоненциално време, ако T(n) е ограничено от O(2nk) за някаква константа k. Ref:Wiki.
