Bagaimana membuktikan bahwa USTCONN membutuhkan ruang logaritmik?

USTCONN adalah masalah yang mengharuskan memutuskan apakah ada jalur dari titik sumber $s$ ke titik target $t$ dalam grafik $G$ , di mana semua ini diberikan sebagai bagian dari input.

Omer Reingold menunjukkan bahwa USTCONN berada di L (doi: 10.1145 / 1391289.1391291 ). Buktinya membangun expander derajat konstan melalui produk zig-zag. Expander derajat konstan memiliki diameter logaritmik dan kemudian dapat memeriksa semua jalur yang mungkin menggunakan jumlah penanda ukuran logaritmik yang konstan.

Hasil Reingold memberikan batas atas logaritmik pada kompleksitas ruang USTCONN, menyelesaikan kompleksitas ruangnya "hingga faktor konstan" menurut makalah tersebut. Saya ingin tahu tentang batas bawah yang sesuai, yang tidak disebutkan di tempat lain di koran.

Bagaimana seseorang membuktikan bahwa ruang logaritmik diperlukan untuk memutuskan USTCONN dalam kasus terburuk?

Edit: Memperbaiki representasi masukan menjadi $N \times N$ adjacency matrix yang mendasari $N$ -vertex grafik simetris sederhana diarahkan, dengan baris terdaftar berturut-turut untuk membentuk $N^2$ -bit string yang.

Lewis dan Papadimitriou menunjukkan (doi: 10.1016 / 0304-3975 (82) 90058-5 ) bahwa USTCONN adalah SL-complete, yang dengan hasil Reingold menyiratkan bahwa SL = L. Savitch menunjukkan (doi: 10.1016 / S0022-0000 (70) 80006-X ) bahwa $\text{NSPACE}(n) \subseteq \text{DSPACE}(n^2)$ . lebih lanjut ( f ( n ) ) = DSPACE ( 1 $\text{DSPACE}(f(n)) = \text{DSPACE}(1)$ untuk fungsi yang dapat dihitung $f(n) = o(\log\log n)$oleh Stearns, Hartmanis dan Lewis (doi: 10.1109 / FOCS.1965.11 ), jadi setidaknya $\Omega(\log\log n)$ ruang diperlukan untuk USTCONN. Akhirnya, kelas-kelas yang biasa dikenal di bawah L (seperti $\text{NC}^1$ ) didefinisikan dalam hal rangkaian dan tidak jelas sebanding dengan kelas mana pun yang didefinisikan dalam batasan ruang.

Sejauh yang saya bisa lihat, ini membuka kemungkinan (diakui tidak mungkin) bahwa ada algoritma deterministik yang lebih baik yang hanya menggunakan $O((\log n)^\delta)$ tetapi $\Omega(\log \log n)$ ruang, untuk beberapa , atau bahkan algoritma nondeterministic untuk USTCONN yang menggunakan ruang .o ( ( log n ) 1 / 2$\delta < 1$$o((\log n)^{1/2})$

Dengan teorema hierarki ruang , selama dapat dibangun-ruang. Ini mungkin menunjukkan bahwa USTCONN tidak boleh dalam .Namun, USTCONN yang lengkap untuk L dalam pengurangan logspace tampaknya tidak menyiratkan hal ini. Tampaknya masih mungkin bahwa USTCONN memiliki struktur yang cukup untuk menyandikan masalah apa pun di L melalui pengurangan ruang log, namun USTCONN sendiri hanya membutuhkan ruang sublogaritmik.f ( n ) DSPACE ( o ( log n ) $\text{DSPACE}(o(f(n)) \subsetneq \text{DSPACE}(f(n))$$f(n)$$\text{DSPACE}(o(\log n))$

Selama ada beberapa bahasa dalam L yang memang membutuhkan ruang logaritmik, maka menunjukkan bahwa USTCONN lengkap untuk L di bawah "pelemahan" ketat daripada pengurangan ruang log akan menghasilkan batas bawah yang diinginkan.

Apakah USTCONN lengkap untuk L dalam pengurangan yang membutuhkan ruang ?$o(\log n)$

Immerman menunjukkan (doi: 10.1137 / 0216051 ) bahwa versi keterjangkauan terarah di mana jalur yang diinginkan (tetapi bukan grafik itu sendiri) bersifat deterministik, lengkap untuk L dalam pengurangan urutan pertama, yang dapat dihitung oleh sirkuit AC . Ini mungkin kemudian diadaptasi untuk menunjukkan bahwa USTCONN lengkap untuk L di bawah FO-reduksi. Namun, meskipun AC benar-benar terkandung dalam L, AC lagi-lagi adalah kelas sirkuit dan saya tidak mengetahui adanya cara untuk melakukan pengurangan-FO dalam ruang sublogaritmik.0 $^0$$^0$$^0$

Sunting 2015-07-14: Ini adalah masalah filosofis yang menarik apakah penggunaan ruang TM harus memasukkan ukuran indeks ke dalam input (sehingga memungkinkan akses acak ke dalam input, tetapi membutuhkan bit tambahan jika inputnya berlipat ganda dalam ukurannya) ), atau apakah ruang yang digunakan oleh TM adalah jumlah kotak worktape yang dikunjungi selama perhitungan (yang mengasumsikan bahwa head tape input sudah diperbaiki dan tidak berubah ketika tape input berukuran dua kali lipat). Definisi gaya RAM sebelumnya segera memberikan logspace batas bawah untuk apa punperhitungan, dan memodelkan komputer saat ini yang melacak posisi saat ini dalam file sebagai offset dari awal file. Definisi klasik yang terakhir mengasumsikan pita mirip kertas dengan kepala bacaan tetap yang tidak tahu apa-apa tentang pita selain simbol masukan saat ini, yang mungkin adalah apa yang dimaksudkan Turing dalam makalah 1937-nya.

Argumen heuristik seperti komentar oleh Thomas, bahwa bahkan tidak mungkin untuk mengindeks input dengan bit ruang, tampaknya mengasumsikan definisi gaya RAM modern. Stearns / Hartmanis / Lewis menggunakan definisi gaya-TM, seperti halnya kebanyakan karya klasik dalam perhitungan ruang-dibatasi.$o(\log n)$

Seseorang dapat membuktikan batas bawah logspace untuk USTCONN yang direpresentasikan sebagai matriks kedekatan dengan mencatat bahwa bahasa unary dari kuadrat sempurna membutuhkan logspace untuk mengenali (lihat Rūsiņš Freivalds, Model Perhitungan, Riemann Hipotesis, dan Matematika Klasik , SOFSEM 1998, LNCS 1521, 89 –106. Doi: 10.1007 / 3-540-49477-4_6 ( pracetak)). Kemudian batas bawah yang sama berlaku untuk USTCONN dengan representasi matriks adjacency. Ini mungkin terlalu banyak cheat: biasanya menegakkan janji dalam masalah janji dimaksudkan untuk menjadi mudah dibandingkan dengan masalah yang sebenarnya, tetapi di sini menegakkan janji bahwa input adalah grafik sudah memberikan batas bawah. Jadi alangkah baiknya untuk melihat argumen untuk logspace batas bawah untuk masalah janji di mana input dijamin berasal dari bahasa .$\{\{0,1\}^{N \times N} \mid N=1,2,\dots\}$

Kertas Quantifiers Menghitung, Hubungan Penerus dan Logaritma Ruang , oleh Kousha Etessami membuktikan bahwa masalah (yang pada dasarnya memeriksa jika simpul mendahului simpul dalam outdegree satu grafik , yang berjanji untuk menjadi jalan ) adalah -bawah di bawah proyeksi gratis kuantifier.$\mathbf{ORD}$$s$$t$$G$$\mathsf{L}$

Masalah dapat dilihat untuk mengurangi ke masalah , oleh -pengurangan: Diberikan contoh dari hapus saja tepi keluar dari dan menampilkan sisi-sisi lainnya sebagai tepi-tepi yang tidak diarahkan pertanyaan menjadi apakah terhubung dalam grafik yang dihasilkan. (Catatan: Pengurangan mungkin bisa dibuat lebih halus.)U S T C O N N F O ⟨ G , s , t ⟩ O R D t u → v { u , v } U S T C O N N s , $\mathbf{ORD}$$\mathbf{USTCONN}$$\mathsf{FO}$$\langle G,s,t\rangle$$\mathbf{ORD}$$t$$u \rightarrow v$$\{u,v\}$$\mathbf{USTCONN}$$s,t$