Apakah LOGLOG = NLOGLOG?

Tentukan LOGLOG sebagai kelas bahasa yang dapat dihitung dalam ruang O (loglog n) oleh mesin Turing deterministik (dengan akses dua arah ke input). Demikian pula mendefinisikan NLOGLOG sebagai kelas bahasa yang dapat dihitung dalam ruang O (log log n) oleh mesin Turing non-deterministik (dengan akses dua arah ke input). Apakah benar-benar tidak diketahui bahwa kelas-kelas ini berbeda?

Saya hanya dapat menemukan beberapa survei yang lebih lama dan teorema bahwa jika mereka sama maka L = NL (yang bukan hanya argumen padding sepele!), Tapi entah bagaimana saya merasa bahwa memisahkan kelas-kelas ini tidak mungkin sulit. Tentu saja saya mungkin benar-benar salah, tetapi jika setiap bit kedua input adalah angka dari 1 ke n dalam urutan meningkat dalam biner, dipisahkan oleh beberapa simbol, maka mesin sudah dapat belajar loglog n dan dengan setiap bit kedua lainnya kita bisa masukan masalah yang bisa mengelabui mesin deterministik tetapi bukan mesin non-deterministik. Saya belum melihat persis bagaimana ini bisa dilakukan tetapi terasa seperti pendekatan yang mungkin, karena dengan trik ini kita pada dasarnya dapat memasukkan log kedalaman dan pohon biner bersama dengan strukturnya alih-alih pita linear biasa.

The masuk dalam kebun binatang kompleksitas yang mengejutkan rinci; itu mengklaim bahwa NLOGLOG = co-NLOGLOG di koran

Komputasi nondeterministik dalam ruang sublogaritmik dan konstribilitas ruang , Viliam Geffert, SIAM Journal on Computing, 1991.

Tetapi setelah membaca singkat, saya tidak melihat adanya klaim tentang fakta bahwa NLOGLOG ditutup dengan komplemen; mungkin diperlukan tampilan yang lebih dalam. Dan hasil utama yang mereka miliki adalah bahwa tidak ada nondeterministic sepenuhnya ruang-constructible monoton terbatas meningkatkan fungsi untuk . Diketahui bahwa jika fungsi tersebut ada, maka$s(n)$$s(n) = o(\log n)$

$\mathsf{SPACE}[s(n)] \neq \mathsf{NSPACE}[s(n)]$ .

Dan dalam kesimpulannya penulis mengklaim bahwa "... masalah pemisahan utama ini tetap terbuka ."

Seperti yang dikatakan @chazisop, hubungan kelas kompleksitas tingkat rendah ini bergantung pada model, dan dinyatakan dalam entri kebun binatang bahwa

"Ada beberapa definisi yang mungkin dari kelas ini; yang paling umum adalah kelas bahasa yang dapat dihitung dalam ruang O (log log n) oleh mesin Turing deterministik dengan akses dua arah ke input."

Yang bertepatan dengan definisi Anda dan juga kertas.