Hirarki ruang bergantian

Hal ini diketahui berkat Immerman dan Szelepcsényi bahwa jika f = Ω ( log ) (bahkan untuk fungsi yang dapat dibangun tanpa ruang).${\rm NSPACE}(f)={\rm coNSPACE}(f)$$f=\Omega(\log)$

Dalam makalah yang sama, Immerman menyatakan bahwa hierarki bolak-balik logspace runtuh, ini berarti bahwa (definisi mesin turing bolak terbatas dan apa yang ada hierarki dapat ditemukan di wikipedia ).$\Sigma_j{\rm SPACE}(\log)={\rm NSPACE}(\log)$

Apakah ada kertas tentang hirarki ruang bergantian untuk ? Saya bertanya minggu lalu kepada Immerman yang tidak ingat membaca hal seperti itu. Dalam bahasa Inggris, saya ingin tahu apakah ada bukti tertulis bahwa menggunakan bahasa apa pun yang dapat diputuskan oleh Mesin Turing dengan pergantian j juga dapat diputuskan oleh mesin turing yang tidak deterministik dengan batas ruang yang sama.$f=\Omega(\log)$$j$

Pertanyaan saya sebenarnya tentang menemukan referensi, karena saya pikir saya sudah menemukan buktinya; tapi saya rasa itu mungkin sudah diketahui.

Mungkin saya harus menyatakan apa yang saya pikir adalah dua masalah utama. Pertama jika , katakanlah f = log 2 , maka tidak mungkin untuk membuat S P A C E ( f ) TM untuk mendapatkan S P A C E ( f ) TM, yang bisa kita lakukan dengan L O G S P A C E TM. Kedua, ada satu argumen untuk kasus f = O ( n $f=O(n)$$f=\log^2$$SPACE(f)$$SPACE(f)$$\rm{LOGSPACE}$$f=O(n)$dan satu untuk tetapi masih ada beberapa masalah untuk fonction yang bukan O ( n ) atau Ω ( n ) .$f=\Omega(n)$$O(n)$$\Omega(n)$

Biarkan - S P A C E ( a ( n ) , s ( n ) ) menjadi kelas masalah yang dapat dipecahkan dengan a ( n ) pergantian dalam ruang s ( n ) . Selama masa kejayaan teori kompleksitas paralel, kelas ini muncul cukup sering.$ALTS$$SPACE(a(n),s(n))$$a(n)$$s(n)$

Sebagai contoh, kelas hanya A L T - S P A C E ( log n , log n ) . Jadi saya membayangkan ada banyak makalah tentang topik Anda, meskipun mungkin tidak ditulis dalam notasi yang Anda gunakan.$AC^1$$ALT$$SPACE(\log n, \log n)$

Untuk sisa pertanyaan Anda, saya pikir seseorang harus dapat membuktikan - S P A C E ( a ( n ) , log n ) ⊆ N S P A C E ( a ( n ) log n ) secara langsung dari Immerman-Szelepcsényi.$ALTS$$SPACE(a(n),\log n) \subseteq NSPACE(a(n) \log n)$

Lebih umum, metode Immerman-Szelepscényi memberikan bahwa ada di N S P A C E ( a ( n ) s ( n ) ) . Gagasan buktinya adalah: Hitung jumlah konfigurasi yang dapat dijangkau dalam pergantian pertama; dari setiap kondisi yang dapat dijangkau tersebut, hitung jumlah konfigurasi yang dapat dicapai dalam pergantian kedua; dan iterate a ( $ALTSPACE(a(n),s(n))$$NSPACE(a(n)s(n))$ kali mundur dalam mode "jelas". Setiap iterasi hanya menggunakan ruang s ( n ) untuk menyimpan jumlah konfigurasi yang dapat dijangkau.$a(n)$$s(n)$

Menggabungkan ini dengan teorema Savitch memberikan hasil sebagai berikut:

Konsekuensi: ada di S P A C E ( ( log n ) 4 ) . Lebih umum, bahasa yang dapat dihitung dalam ruang polylogarithmic dengan banyak pergantian polylogarithm secara komputable dalam waktu polylogarithmic deterministik.$ALTSPACE(\log n, \log n)$$SPACE((\log n)^4)$

Akibat wajar: Demikian pula, bahasa yang dapat dihitung dalam ruang polinomial dengan banyak alternatif secara polinomi berada dalam ruang polinomial deterministik.

$ALTSPACE$$STA$

[B] L. Berman, "Kompleksitas Teori Logika", Ilmu Komputer Teoritis 11 (1980) 71-77.