Bisakah

Pertimbangkan bahasa $\mathtt{EQUALITY} = \{ a^nb^n \mid n \geq 0 \}$ .

Diketahui bahwa $\mathtt{EQUALITY}$ tidak dapat dikenali oleh mesin Turing (ATM) sublogaritmik yang bergantian (Szepietowski, 1994) . (Ada ATM yang menggunakan ruang sublogaritmik untuk anggota tetapi tidak untuk semua bukan anggota!)

Di sisi lain, Freivalds (1981) menunjukkan bahwa mesin Turing probabilistik ruang-terikat-kesalahan-konstan (PTMs) dapat mengenali $\mathtt{EQUALITY}$ tetapi hanya dalam waktu yang diharapkan secara eksponensial ( Greenberg dan Weiss, 1986 ). Kemudian, itu menunjukkan bahwa tidak ada yang dibatasi-kesalahan $o(\log\log n)$ -space PTM bisa mengenali bahasa non-reguler di waktu yang diharapkan polinomial ( Dwork dan Stockmeyer, 1990 ). Pertanyaanku adalah

apakah PTMs ruang-sublogaritmik poly-time mengenali $\mathtt{EQUALITY}$ dengan bounded-error.

Saya telah menemukan jawaban untuk pertanyaan saya sendiri. Hasilnya diberikan dalam Bagian 5 dari Karpinski dan Verbeek, 1987 .

$n$$\Theta(\log \log n)$$a$$n$$b$$m$$O(\log \log n)$

$n \neq m$$\exists k \leq 4 \log(n+m)$$n \not\equiv m \mod k$O ( log log n ) O ( log log n ) k n ≠ m $k$$O(\log \log n)$$O(\log \log n)$$k$$n \neq m$$1 \over 2$