Mengapa seseorang sering membutuhkan ruang konstruksi dalam teorema Savitch?

Ketika teorema terkenal Savitch dinyatakan, orang sering melihat persyaratan bahwa dapat dibangun dalam ruang (yang menariknya, dihilangkan dalam Wikipedia). Pertanyaan sederhana saya adalah: Mengapa kita membutuhkan ini? Saya mengerti persyaratan untuk berada di , yang jelas dari buktinya. Tapi tidak ada bukti yang saya lihat sejauh ini secara eksplisit menggunakan bahwa adalah ruang yang dapat dibangun.$S(n)$$S(n)$$\Omega(\log n)$$S(n)$

Penjelasan saya: untuk memanggil prosedur REACH (atau PATH atau apa pun yang Anda suka menyebutnya), parameter terakhir perlu "dijabarkan", dan agar tidak meninggalkan batas ruang S (n) untuk satu panggilan , kita tidak perlu lebih dari ruang untuk menuliskannya.$S(n)$

Saya yakin penjelasan Anda benar. Subrutin ST-REACH mendapat sebagai input, dan menemukan apakah dapat dijangkau dari dengan langkah-langkah . dan akan menjadi konfigurasi awal dan akhir, dan , batas atas pada jumlah konfigurasi yang berbeda.$(s,t,\ell)$$t$$s$$\ell$$s$$t$$\ell=2^{O(s(n))}$

Untuk mengatur kita harus dapat menghitung (atau lebih tepatnya, ). Jika proses ini membutuhkan lebih dari ruang , maka seluruh mesin akan memiliki ruang lebih dari yang diizinkan. Mungkin bahkan terlalu banyak karena panggilan rekursif ke st-REACH (apakah ada alasan lain yang mungkin?), Tetapi saya tidak memeriksanya.$\ell$$s(n)$$2^{O(s(n))}$$O(s^2(n))$$O(s^2(n))$

Ini diuraikan dengan baik dalam buku teks Teori Komputasi Dexter Kozen, dalam bab 2.

Teorema Savitch (Teorema 1 dalam makalahnya) mengatakan: jika , maka . Konstrukrabilitas ruang sering dianggap diasumsikan sebagai bukti, tetapi persyaratan ini dapat dihapus dengan memulai kembali pencarian dengan batas ruang tetap yang diizinkan untuk meningkat dengan setiap upaya.$S(n) \ge \log n$$\text{NSPACE}(S(n)) \subseteq \text{DSPACE}(S(n)^2)$

Kebingungan mungkin muncul karena makalah Savitch asli sebagian besar tentang menyelidiki apakah . Oleh karena itu ia menghabiskan banyak upaya pada fungsi-fungsi yang dapat dibangun-ruang, karena pengamatan berikut dari makalah ini:$\text{NSPACE}(S(n)) \not\subseteq \text{DSPACE}(S(n))$

Wajar untuk bertanya apakah ada fungsi penyimpanan yang kelas kompleksitas deterministik dan nondeterministiknya sama. Jawabannya diberikan oleh Manuel Blum dan "ya". Blum menunjukkan bahwa ada fungsi penyimpanan besar yang sewenang-wenang L (n) sedemikian sehingga satu set diterima dalam penyimpanan deterministik L (n) jika, dan hanya jika, ia diterima dalam penyimpanan L (n) non-deterministik. Fungsi-fungsi ini L (n) tidak, bagaimanapun, "berperilaku baik" dan Teorema 3 tidak berlaku untuk mereka.

(Di sini "berperilaku baik" mengacu pada fungsi ruang-dibangun, yang disebut terukur oleh Savitch.)