Duże luki między pamięcią RAM a złożonością maszyny Turinga

Jeśli weźmiemy pod uwagę tylko problemy w P, czy są jakieś duże luki między najszybszym znanym algorytmem RAM-słowo i najszybszym znanym algorytmem maszyny Turinga dla określonych problemów? Jestem szczególnie zainteresowany, jeśli istnieją duże luki w naturalnych problemach leżących w interesie ogólnym.

Wiadomo, że każdy problem, który można obliczyć na maszynie RAM w czasie , można to zrobić na maszynie Turinga w czasie co najwyżej . Musisz zauważyć, że całkowity rozmiar używanej pamięci nie może być większy niż , ponieważ oznaczałoby to, że wykonałeś więcej operacji zapisu niż , więc za każdym razem, gdy pobierasz coś z pamięci RAM, Turing maszyna zajęłaby w najgorszym przypadku czas, aby znaleźć żądany element sekwencyjnie z taśmy. Poza dostępem do pamięci pozostałe operacje powinny zająć mniej więcej ten sam czas. I tak dostajesz granicę.$T(n)$$T(n)^2$$T(n)$$T(n)$$T(n)$

Poniższy przykład pokazuje, że algorytm który wymaga do rozwiązania problemu z ramą słów, może wymagać na 1-taśmowej maszynie Turinga (TM) ), która dokładnie wykonuje wszystkie obliczenia wskazane przez . Rozumiem, że pytanie dotyczy 1-taśmy TM i używam tego tylko w mojej odpowiedzi. To jest edycja, aby odpowiedzieć na uwagi Emila Jeřábka.$A$$O(n\log(n))$$O(n^2 \log(n)^3)$$A$

Znajdziemy następujący bardziej ogólny wniosek . Aby udowodnić, że TM może rozwiązać w problem rozwiązany w przez algorytm na pamięci RAM, nie wystarczy uruchomić na TM. Mądry może być potrzebny algorytm. To samo dotyczy sytuacji, gdy ktoś chce udowodnić narzut . W każdym razie udowodnienie istnienia sprytnego algorytmu wydaje się być dalekie od natychmiastowego. Nie jest to zgodne z innymi odpowiedziami, które w zasadzie proponują jedynie symulację / wykonanie na TM wszystkich obliczeń pamięci RAM (algorytmu ) w celu ogłoszenia złożoności TM, takiej jak$O(T(n)^2)$$O(T(n))$$A$$A$$O(n\log(n))$$A$$O(T(n)^2)$ lub .$O(T(n)n\log(n))$

Problem: tablicę / tabelę z liczb całkowitych, każda zapisana w bitach. Otrzymujemy drugą tablicę z pozycjami , z których każda rejestruje pewną liczbę bitów. Dla dowolnego definiujemy if MOD MOD . W przeciwnym razie . Wyjście . Uważam, że dane wejściowe podano jako taśmę z$\texttt{tab}$$n=2k$$\log(n)$$\texttt{d}$$\log(n)$$\log(n)$$t\in[0..\log(n)-1]$$X_t=1$$\texttt{tab}[i]$$\texttt{d}[t]=\texttt{tab}[n/2+i]$$\texttt{d}[t]~\forall i\in [0..n/2-1]$$X_t=0$$\sum_{t=0}^{\log(n)-1} X_t$$n\log(n)+\log(n)\log(n)$ cyfry binarne, aby odpowiedzieć na komentarze Emila Jeřábka.

Algorytm w pamięci RAM$A$ A Pamięć RAM o rozmiarze słowa potrzebuje = do odczytu wejściowego ciągu binarnego dane. Ale po odczytaniu danych może działać tylko ze słowami o rozmiarze . Algorytm oblicza dowolne w , przechodząc przez wszystkie i testując warunek. Główna pętla to FOR : oblicz . Całkowita złożoność wynosi (odczyt danych) +$w=\log(n)$$O(n\log(n)+\log(n)^2)$$O(n\log(n))$$\log(n)$$A$$X_t$$O(n)$$i\in [0..n/2-1]$$A$$t=0, 1, 2, \dots \log(n)-1$$X_t$$O(n\log(n))$$O(n\log(n))$(wykonując obliczenia), więc może zrobić to wszystko w na RAM.$A$$O(n\log(n))$

Algorytm na TM na 1 taśmę:$A$ Twierdzę, że TM na jedną taśmę potrzebuje czasu na ustalone . Z punktu widzenia TM określenie jest równoważne testowaniu równości dwóch ciągów binarnych o długości . Na przykład operacja MOD MOD może być równoważna usunięciu bitu z . W takich przypadkach ustalenie jest równoważne testowi równości na ciągach bitów o długości . Dobrze wiadomo, że testowanie równości dwóch łańcuchów długości$O(n^2 \log(n)^2)$$t$$A_t$$O(n\log(n))$$\texttt{tab}[i]$$\texttt{d}[t]$$0$$\texttt{tab}[i]$$A_t$$n(\log(n)-1)/2$$m$wymaga na 1-taśmie TM, ale tak naprawdę nie mogę teraz znaleźć odniesienia. Jednak dostarczam dowód w ps. Jeśli TM wykonuje główną pętlę z , musi wydać co najmniej dla każdego , kończąc się w .$O(m^2)$$A$$O((n\log n)^2)$$t=0, 1, 2, \dots \log(n)-1$$O(n^2 \log(n)^3)$

ps. Pokazuję, że testowanie równości na ciągach bitów z bitami nie może być szybsze niż testowanie palyndromu na ciągach bitów z bitami (wiadomo, że palyndrom zajmuje co najmniej czas ). Możemy zmodyfikować dowolny algorytm TM do testowania równości w celu rozwiązania palindromu. Załóżmy, że TM testująca równość rozpoczyna się od dwóch liczb całkowitych: jednej po lewej stronie głowy, jednej po prawej (jest to najprostsza forma wprowadzania TM). Każdy ruch nad lewymi pozycjami może być odzwierciedlony (odbity) nad prawymi pozycjami. Budujemy lustrzaną bazę TM: ilekroć początkowa baza TM znajduje się w pozycji (po lewej), lustrzana baza TM znajduje się w pozycji (po prawej). Jeżeli TM rozwiązała test równości w mniej niż$m$$m$$O(m^2)$$-x<0$$x$$O(m^2)$, ta zmodyfikowana lustrzana TM rozwiązałaby palindrom w mniej niż .$O(m^2)$

Ponadto istnieją pewne algorytmy TM do testowania równości i wszystkie z nich wymagają kwadratowego czasu, ponieważ wymagają trochę zygzakowatości, patrz na przykład Turing Machine Przykład 2 na kursy.cs.washington.edu/courses/cse431/14sp/scribes/ lec3.pdf