Редукцията полиномно време ли е?

2024 Автор: Fiona Howard | [email protected]. Последно модифициран: 2024-01-10 06:34

В теорията на изчислителната сложност, намаляването на полиномното време е метод за решаване на един проблем с помощта на друг. Редукциите с полиномно време често се използват в теорията на сложността за дефиниране както на класове на сложност, така и на пълни проблеми за тези класове. …

Какво се счита за полиномиално време?

За един алгоритъм се казва, че е с полиномиално време, ако времето му за изпълнение е горно ограничено от полиномен израз в размера на входа за алгоритъма, тоест T(n)=O(n^k) за някаква положителна константа k.

Как да разберете дали нещо е полиномно време?

3 отговора. Алгоритъмът е полиномиален (има полиномно време на работа), ако за някое k, C>0, времето му на работа на входове с размер n е най-много Cnk. Еквивалентно, алгоритъмът е полином, ако за някакъв k>0 времето му на работа на входове с размер n е O(nk).

Какво се случва, ако намаляването е разрешено в експоненциално време?

Ако намаляването е разрешено експоненциално време, тогава то може напълно да реши първоначалния проблем и да създаде тривиален екземпляр на целевия проблем Това означава, че всеки проблем в NP е сведен до всеки друг проблем от такъв тип редукции, така че всеки проблем в NP е NP-завършен за експоненциално намаляване на времето.

Какво е експоненциален алгоритъм?

За един алгоритъм се казва, че е експоненциално време, ако T(n) е горна граница с 2^{poly( )} , където poly(n) е някакъв полином от n. По-формално, алгоритъмът е експоненциално време, ако T(n) е ограничено от O(2^{nk) за някаква константа k. Ref:Wiki.}