W teorii złożoności obliczeniowej redukcja wielomianowa jest metodą rozwiązywania jednego problemu za pomocą innego. Redukcje wielomianowe są często używane w teorii złożoności do definiowania zarówno klas złożoności, jak i kompletnych problemów dla tych klas. …
Co jest uważane za czas wielomianowy?
O algorytmie mówi się, że działa w czasie wielomianowym, jeśli jego czas działania jest ograniczony od góry przez wyrażenie wielomianowe o rozmiarze danych wejściowych algorytmu, to znaczy T(n)=O(nk) dla pewnej dodatniej stałej k.
Skąd wiesz, że coś jest czasem wielomianowym?
3 Odpowiedzi. Algorytm jest wielomianowy (ma czas działania wielomianu), jeśli dla pewnego k, C>0, jego czas działania na wejściach o rozmiarze n wynosi co najwyżej Cnk. Równoważnie algorytm jest wielomianowy, jeśli dla niektórych k>0 jego czas działania na wejściach o rozmiarze n wynosi O(nk).
Co się stanie, jeśli redukcja jest dozwolona w czasie wykładniczym?
Jeżeli redukcja jest dozwolona w czasie wykładniczym, wtedy może to w pełni rozwiązać pierwotny problem i stworzyć trywialną instancję problemu docelowego Oznacza to, że każdy problem w NP można zredukować do każdego inny problem przez tego typu redukcje, więc każdy problem w NP jest NP-zupełny dla wykładniczych redukcji czasu.
Co to jest algorytm wykładniczy?
Algorytm mówi się o czasie wykładniczym, jeśli T(n) jest ograniczone od góry przez 2poli( ) , gdzie poli(n) jest jakimś wielomianem w n. Bardziej formalnie, algorytm jest wykładniczy, jeśli T(n) jest ograniczone przez O(2nk) dla pewnej stałej k. Ref:Wiki.
