Hirarki ruang bergantian

13

Hal ini diketahui berkat Immerman dan Szelepcsényi bahwa jika f = Ω ( log ) (bahkan untuk fungsi yang dapat dibangun tanpa ruang).NSPACE(f)=coNSPACE(f)f=Ω(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 ).ΣjSPACE(log)=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=Ω(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=log2SPACE(f)SPACE(f)LOGSPACEf=O(n)dan satu untuk tetapi masih ada beberapa masalah untuk fonction yang bukan O ( n ) atau Ω ( n ) .f=Ω(n)O(n)Ω(n)

Arthur MILCHIOR
sumber
2
Akan sangat membantu jika Anda dapat memasukkan definisi pendek dari dua hierarki yang Anda sebutkan.
Robin Kothari
hilang an 's' dalam hierarki
Suresh Venkat
Saya menambahkan tautan untuk pergantian dan hierarki ruang terbatas, dan definisi cepat dalam bahasa Inggris tentang apa yang saya inginkan. Untuk hiearchie oracle saya khawatir definisi yang tepat mungkin terlalu lama, dan lagi pula tidak berguna karena kelas ini sama dengan ruang log non deterministik.
Arthur MILCHIOR
singular hierarki adalah hierarki, btw. bisakah kamu mengedit itu?
Suresh Venkat
Diedit. Saya khawatir saya tidak pernah memperhatikannya.
Arthur MILCHIOR

Jawaban:

7

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.ALTSSPACE(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.AC1ALTSPACE(logn,logn)

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.ALTSSPACE(a(n),logn)NSPACE(a(n)logn)

Ryan Williams
sumber
Terima kasih; ini tampaknya sangat menjanjikan. Saya hanya tidak tahu harus mulai dari mana untuk mencari artikel seperti itu. Buktinya sepertinya tidak sepele bagi saya karena, biarkan M menjadi TM dalam ASPACE (f, 2), biarkan M1 menjadi bagian eksistensial dan M2 bagian universal. Kita tidak dapat lagi menganggap M2 sebagai coSPACE (f) = SPACVE (f) TM karena kita harus mengambil input M1 dalam pita input. Tapi ya, tentu ada sesuatu yang harus dilakukan dengan menggunakan bukti langsung mereka. Bahkan jika saya tidak menggunakan nomor "a (n)" dari pergantian. Sekali lagi terima kasih
Arthur MILCHIOR
9

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 ( nALTSPACE(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(logn,logn)SPACE((logn)4)

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

ALTSPACESTA

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

Sam Buss
sumber