Wiki definiują Czas wielomianowy jako odłogowany:
Mówi się, że algorytm jest wielomianowy, jeśli jego czas działania jest ograniczony przez wyrażenie wielomianowe w wielkość wejścia algorytmu, tj. $ T (n) = O (n ^ k) $ dla jakiejś stałej $ k $
I rozumiem, że ogólnie rzecz biorąc różnica między Czasem wielomianowym i Czas wykładniczy jest taka, że funkcja wykładnicza rośnie ściśle szybciej niż jakakolwiek funkcja wielomianowa, asymptotycznie ( odniesienie ).
Próbuję zrozumieć sedno definicja Czas wykładniczy .
- Jakie elementy utworzą jeden algorytm do działania w Czas wykładniczy ?
- Jaką zmianę muszę wprowadzić w wyrażeniu wielomianowym aby to Czas wykładniczy ? (Przez to mam na myśli definicję algorytmu na początku pytania)
Komentarze
- 1. Rób wiele rzeczy wykładniczo. 2. Użyj wielomianu jako potęgi podstawy > 1.
- Nie ' nie rozumiem twojej sekundy pytanie. Wielomiany to wielomiany; wykładnicze są wykładnicze. Pytanie, co trzeba zmienić, aby przekształcić wielomian w wykładniczy, jest jak pytanie, co trzeba zmienić, aby przekształcić logarytm w cosinus.
- @DavidRicherby Czy będą wykładnicze funkcje czasu, jeśli P = NP? Jak można zdefiniować wykładniczą funkcję czasu za pomocą wyrażenia wielomianowego?
- Funkcje wykładnicze z pewnością będą nadal istnieć, jeśli P = NP. Prawdopodobnie nadal występują problemy, które ' będą wymagały czasu wykładniczego, nawet jeśli P = NP, chociaż żaden od razu nie przychodzi na myśl. Funkcję wykładniczą można zdefiniować za pomocą wielomianu, ale ten wielomian musi być nieskończenie długi – możesz chcieć sprawdzić Rozszerzenia Taylora, jeśli ' jesteś tym zainteresowany.
- @ymbirtt Nawet najłatwiejsza wersja twierdzenia o hierarchii czasowej mówi, że nie ma algorytmu czasu wielomianowego dla żadnego problemu z zakończeniem EXPTIME. To ' jest bezwarunkowym wynikiem: nie ' nie zależy od założenia, że P $ \ neq $ NP.
Odpowiedź
-
Nie ma łatwej odpowiedzi na to pytanie, chociaż istnieją znaki, na które należy zwrócić uwagę . Na przykład badanie każdego możliwego podzbioru zbioru jest wykładnicze – więc gdybym miał zbiór liczb całkowitych $ \ {x_1, …, x_n \} $ i chciałbym sprawdzić każdy podzbiór, aby sprawdzić, czy sumują się do $ 0 $, musiałbym wziąć pod uwagę dokładnie $ 2 ^ n $ podzbiory, co powoduje, że ta metoda jest wykładniczym czasem. Kilka różnych pułapek może jednak spowodować wykładniczy czas algorytmu, więc zamiast szukać szerszych kategorii, przeanalizuj algorytmy indywidualnie dla każdego przypadku.
-
Jeśli algorytm wykonuje $ n ^ 2 $ kroków, to jest to wielomian. Jeśli zajmuje $ 2 ^ n $ kroków, jest wykładniczy. Różnica polega na położeniu $ n $. Jeśli coś jest $ O (n ^ m) $ dla $ n > 1 $, $ m > 0 $, to „s wielomian w $ n $ dla ustalonych $ m $, ale wykładniczy w $ m $ dla ustalonych $ n $.
Komentarze
- Ostrożnie. Funkcja $ n ^ m $ isn ' t wielomian w $ n $, chyba że $ m $ jest stałą. A jeśli $ m $ jest stała, nie ' nie ma sensu mówić, że funkcja jest wykładnicza w tej stałej.
- Tak, ' wróć do prawej. ' wyjaśnię to.
Odpowiedź
Często, gdy rozważasz problem i wyliczasz całą jego przestrzeń poszukiwań, otrzymujesz wykładniczy algorytm czasowy brutalnej siły. Zwykle myślisz o problemach z podzbiorem (w SAT wybierasz podzbiór zmienne ustawione na true), problemy z permutacjami (w TSP, każda trasa jest permutacją miast) i problemy z partycjami (w kolorowaniu grafu, próbujesz p podziel wierzchołki na klasy kolorów). Lub rozważ nawet sortowanie: istnieje $ n! $ Permutacji $ n $ liczb całkowitych. Przejrzyj wszystkie permutacje i sprawdź, czy są posortowane. Głupie (i powolne), ale działa.
Komentarze
- Pamiętaj, że $ O (n!) $ Jest nawet gorsze niż $ O ( k ^ n) $. Jeśli ' nadal próbujesz dowiedzieć się o złożoności czasowej, może to być przydatna rzecz, aby udowodnić sobie.