Dlaczego czas wielomianowy nazywany jest „wydajnym”?

Dlaczego w informatyce jakakolwiek złożoność, która jest co najwyżej wielomianowa, jest uważana za wydajną?

Dla każdego praktycznego zastosowania ^(a) algorytmy o złożoności są znacznie szybsze niż algorytmy działające w czasie, powiedzmy n 80 , ale pierwszy jest uważany za nieefektywny, a drugi jest wydajny. Gdzie jest logika ?!$n^{\log n}$$n^{80}$

^{(a) Załóżmy na przykład, że liczba atomów we wszechświecie wynosi około .$10^{80}$}

Inna perspektywa „wydajności” polega na tym, że czas wielomianowy pozwala nam zdefiniować pojęcie „wydajności”, które nie zależy od modeli maszyn. W szczególności istnieje wariant tezy Turinga zwany „skuteczną tezą Turinga”, który mówi, że każdy problem, który działa w czasie wielomianowym na rodzaju modelu maszyny, będzie również działał w czasie wielomianowym na innym równie potężnym modelu maszyny.

Jest to słabsze stwierdzenie w stosunku do ogólnej tezy CT i jest „niejako” naruszane zarówno przez algorytmy randomizowane, jak i algorytmy kwantowe, ale nie zostało naruszone w sensie możliwości rozwiązania problemu trudnego dla NP w czasie wieloczasowym poprzez zmianę model maszyny.

To jest ostatecznie powód, dla którego czas wielomianowy jest popularnym pojęciem w teorii CS. Jednak większość ludzi zdaje sobie sprawę, że nie odzwierciedla to „praktycznej wydajności”. Więcej informacji na ten temat zawiera post Dicka Liptona na temat „ algorytmów galaktycznych ”.

$O(n^{80})$$O(n^{\log n})$$n > 1208925819614629174706176$

$n^{\log n}$$n^{80}$

Na przykład większość bibliotek do mnożenia liczb całkowitych, np. GMP wdroży mieszankę algorytmów i wybierze gorszy algorytm na podstawie wielkości wejściowej, wybierze praktycznie lepsze algorytmy na podstawie wielkości wejściowej, chociaż algorytmy te mogą być asymptotycznie gorsze. Niektóre asymptotycznie „gorsze” algorytmy będą szybsze przy pewnych rozmiarach wejściowych i zostaną wybrane w stosunku do algorytmów optymalnych.

$O(n^{2.3737})$

Teoria TL; DR dba o zachowanie asymptotyczne w celu porównania algorytmów, ponieważ granica wielkości wejściowej idzie do dowolnie dużych liczb.

Ta odpowiedź przyjrzy się szerszemu kontekstowi twojego pytania. Informatyka jest w rzeczywistości stosunkowo młodą i nieco otwartą nauką i nie ma jeszcze dobrych ani nawet dobrych odpowiedzi na niektóre podstawowe i podstawowe pytania. Podstawowe pytanie „co jest skutecznie obliczane” jest dokładnie lub z grubsza sformalizowane w CS (w zależności od opinii) jako słynny problem P vs NP (lub ściśle powiązany problem P vs Exptime) i nadal jest otwarty po ponad czterdziestu latach początkowo wprowadzony przez Cooka / Levina ~ 1970 i intensywna praca największych światowych informatyków (i wielu matematyków jest również zainteresowanych problemem jako podstawowym).

Innymi słowy, nawet przy zgrubnej definicji „wydajnego” jako czasu P i jednej z najwyżej cenionych nagród naukowych - mianowicie nagrody 1 mln USD związanej z problemem od ponad 10 lat - informatyka nie może nawet udowodnić, że pewne problemy (zbliżone do ta granica) musi lub nie musi mieć wydajnych algorytmów (Ptime). Dlatego dokładna definicja „wydajnego” bardziej precyzyjnego niż czas P nie jest w tym momencie konieczna ani nawet możliwa . Jeśli / kiedy hipoteza P kontra NP zostanie rozstrzygnięta w taki czy inny sposób, możliwe lub prawdopodobnie będzie możliwe bardziej rygorystyczne określenie „wydajnego”.

Co więcej, można by pomyśleć, że definicja „wydajnego” czasu Ptime może być nawet nieco „niechlujna”, a większość informatyków prawdopodobnie by się zgodziła i prawie wszyscy uważają, że hipoteza P kontra NP ma ogromne znaczenie dla rozstrzygnięcia punkt, w którym mogliby nawet uznać to twierdzenie lub obserwację za trywialne ... innymi słowy, że tak powiem, jest to praca w toku / pracujemy nad tym . (w rzeczywistości główni informatycy posunęli się nawet tak daleko, tylko na pół żartem, rutynowo nazywając lukę i brak postępów / ostatecznych separacji zakłopotaniem ).

W rzeczywistości istnieje nawet blisko spokrewniona / znacznie silniejsza hipoteza niż P vs NP, a mianowicie NP vs P / poli, których w tej chwili nie może rozwiązać również informatyka. Przypuszcza, że ​​problemów czasu NP nie można rozwiązać za pomocą żadnych obwodów „P”, tzn. nawet nie ograniczając się do tych obwodów, które mogą być tworzone przez algorytmy / maszyny Turinga.

Co do tego, jak trudne może być P w porównaniu z NP - istnieje uzasadniony powód, by sądzić, że może być co najmniej tak trudny, jak bardzo stara hipoteza Riemanna w matematyce (obecnie 1,5 wieku ), ponieważ obaj otrzymali tę samą nagrodę w wysokości 1 miliona dolarów za ponad dekada i żadne z nich nie zostało jeszcze rozwiązane / pierwsze.

Innymi słowy, precyzyjne określenie, które algorytmy są naprawdę „wydajne”, jest w rzeczywistości jednym z najważniejszych i najtrudniejszych istniejących otwartych problemów w nauce teoretycznej i matematyce .

W rzeczywistości pytanie „co jest efektywnie obliczane” jest w rzeczywistości jeszcze bardziej subtelne, ponieważ istnieje wariant tezy Turinga zwany tezą CT czasu P i nie wiadomo, czy obliczenia kwantowe faktycznie ją naruszają . Biorąc pod uwagę przełomowy wynik QM w P-time, faktoring był uważany za dramatyczny zwrot w tych badaniach. Innymi słowy, problem tego, co jest skutecznie obliczane, w rzeczywistości prawdopodobnie sprowadza się do zasad głębokiej fizyki i dotyczy tego, czy obliczenia kwantowe mogą obliczać wydajniej niż obliczenia klasyczne, co jest również ogólnie otwartym problemem w teoretycznej CS i zaawansowanej fizyce.

Można więc nawet dodać, że P vs NP i kwestia wydajnego przetwarzania mogą mieć kluczowe lub fundamentalne znaczenie dla - oprócz CS i matematyki - fizyki .

[1] P vs NP problem, wikipedia

[2] Problemy z nagrodami Millenium

[3] Klasa P / Poly, wikipedia

[4] Algorytm Shora

Algorytmy czasowe wielomianowe są uważane za wydajne tylko w porównaniu z najtrudniejszym czasem niepolarnym, zwłaszcza tak zwane NP-Complete. Zobacz obraz: Schemat Eulera dla zestawu problemów P, NP, NP-zupełny i NP-twardy .