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?

cc.complexity-theory time-complexity space-complexity space-time-tradeoff 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

Ile czasu rozpoznaje palindromy w przestrzeni logarytmicznej?

Odpowiedzi: