Ile czasu rozpoznaje palindromy w przestrzeni logarytmicznej?

20

Dobrze wiadomo, że palindromy można rozpoznać w czasie liniowym na maszynach Turinga z taśmami, ale nie na maszynach Turinga z pojedynczą taśmą (w takim przypadku potrzebny czas jest kwadratowy). Algorytm czasu liniowego wykorzystuje kopię danych wejściowych, a zatem wykorzystuje również przestrzeń liniową. $2$

Czy potrafimy rozpoznać palindromy w czasie liniowym wielowarstwowej maszyny Turinga, używając tylko przestrzeni logarytmicznej? Mówiąc bardziej ogólnie, jaki rodzaj kompromisu czasoprzestrzennego znany jest z palindromów?

— Bruno
źródło

22

Używając sekwencji krzyżujących lub złożoności komunikacyjnej, łatwo jest uzyskać kompromis dla sekwencyjnej maszyny Turinga wykorzystującej czas i przestrzeń . $T(n)S(n) = \Omega(n^2)$ $O(T(n))$ $O(S(n))$

Ten wynik został po raz pierwszy uzyskany przez Alana Cobhama, wykorzystując sekwencje krzyżowania w pracy Problem rozpoznawania zestawu idealnych kwadratów, który pojawił się w SWAT (później FOCS) 1966.

— Kristoffer Arnsfelt Hansen
źródło

25

Możesz użyć tego samego argumentu, który posłużył do udowodnienia czasu na pojedynczej taśmie. $\Omega(n^2)$

Załóżmy, że masz bazę TM ze spacją która rozpoznaje palindromy $S(n)$ (gdziejest odwrotnością) w czasie. Gdy głowa (wejściowa) przecina środkową, może przenosić tylkobitów informacji. Musi więc wykonaćkrzyże, a każdy krzyż wymaga czasu. $\{x\,0^{\frac{n}{3}} x^R \mid |x|=n/3 \}$ $x^R$ $x$ $T(n)$ $0^{n/3}$ $S(n)$ $\Omega(n / S(n))$ $n/3$

Więc . $T(n)S(n)=\Omega(n^2)$

— Marzio De Biasi
źródło

Operacje ... po napisaniu odpowiedzi zobaczyłem, że Kristoffer już opublikował rozwiązanie. Akceptuje jego odpowiedź, zostawiam moją tylko dlatego, że ma ona kilka dodatkowych szczegółów.

— Marzio De Biasi

5

Myślę, że było to praktycznie jednoczesne.

— Kristoffer Arnsfelt Hansen

Jak zasugerowałeś, zaakceptowałem odpowiedź Kristoffera, ponieważ był nieco wcześniej ... Dzięki wam obojgu!

— Bruno,

1

wygląda dziwnie. Lepiej

{x 0^{\frac{n}{3}} x^{R} ∣ | x | = | y | = n / 3}

$\{x0^{\frac{n}{3}} x^R \mid |x|=|y|=n/3 \}$

adnotacja, że

{x 0^{\frac{n}{3}} x^{R} ∣ | x | = n / 3}

$\{x0^{\frac{n}{3}} x^R \mid |x|=n/3 \}$

jest operatorem odwracania łańcucha.

^{R}

${}^R$

— miracle173

2

Oprócz innych odpowiedzi warto zauważyć, że jeśli dozwolona jest randomizacja, palindromy można rozpoznać za pomocą spacji O (1) i czasu O (n), mieszając lewą stronę łańcucha, mieszając transpozycję prawej strony ciąg i sprawdzanie, czy wartości skrótów są równe. Nie powinno to być trudne na maszynie Turinga.

— pierożek Mobiusa
źródło