Berapa banyak waktu untuk mengenali palindrom di ruang logaritmik?

20

Sudah diketahui bahwa palindrom dapat dikenali dalam waktu linier pada mesin Turing pita, tetapi tidak pada mesin Turing pita tunggal (dalam hal ini waktu yang dibutuhkan adalah kuadratik). Algoritma linear-waktu menggunakan salinan input, dan dengan demikian juga menggunakan ruang linier. $2$

Bisakah kita mengenali palindrom dalam waktu linier dari mesin Turing multitape, hanya menggunakan ruang logaritmik? Secara umum, pertukaran ruang-waktu seperti apa yang dikenal dengan palindrom?

cc.complexity-theory time-complexity space-complexity space-time-tradeoff Bruno
sumber

22

Dengan menggunakan urutan persimpangan atau kompleksitas komunikasi, mudah untuk memperoleh tradeoff untuk mesin Turing berurutan menggunakan waktu dan spasi . $T(n)S(n) = \Omega(n^2)$ $O(T(n))$ $O(S(n))$

Hasil ini pertama kali diperoleh oleh Alan Cobham menggunakan urutan persimpangan di kertas . Masalah pengenalan untuk himpunan kotak sempurna yang muncul di SWAT (kemudian FOCS) 1966.

Kristoffer Arnsfelt Hansen
sumber

25

Anda dapat menggunakan argumen yang sama yang digunakan untuk membuktikan waktu terikat pada rekaman tunggal. $\Omega(n^2)$

Misalkan Anda memiliki TM dengan ruang yang mengenali palindrom (di mana adalah kebalikan dari ) dalam waktu . Ketika kepala (input) melintasi tengah ia hanya dapat membawa bit informasi. Jadi perlu membuat persilangan , dan setiap persilangan membutuhkan waktu . $S(n)$ $\{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$

Jadi . $T(n)S(n)=\Omega(n^2)$

Marzio De Biasi
sumber

Ops ... setelah menulis jawabannya saya melihat bahwa Kristoffer sudah memposting solusinya. Menerima jawabannya, saya meninggalkan milik saya hanya karena memiliki beberapa detail lagi.

Marzio De Biasi

5

Saya kira itu secara simultan.

Kristoffer Arnsfelt Hansen

Seperti yang Anda sarankan, saya menerima jawaban Kristoffer karena dia sedikit lebih awal ... Terima kasih untuk kalian berdua!

Bruno

1

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

$\{x0^{\frac{n}{3}} x^R \mid |x|=|y|=n/3 \}$ terlihat aneh. Lebih baik anotasi bahwa adalah operator string terbalik.

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

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

^{R}

${}^R$

miracle173

2

Selain jawaban lain, perlu dicatat bahwa jika pengacakan diizinkan, palindrom dapat dikenali dengan O (1) ruang dan waktu O (n) dengan hashing sisi kiri string, hashing transpos sisi kanan string. string, dan memeriksa apakah hash sama. Seharusnya tidak sulit untuk melakukan ini pada mesin Turing.

pangsit mobius
sumber

Berapa banyak waktu untuk mengenali palindrom di ruang logaritmik?

Jawaban: