NTIME (f) bagian dari DSPACE (f)

Seperti yang dinyatakan dalam pertanyaan, bagaimana kita membuktikan bahwa ? $\textbf{NTIME}(f(n)) \subseteq \textbf{DSPACE}(f(n))$

Adakah yang bisa mengarahkan saya ke bukti atau menguraikannya di sini? Terima kasih!

complexity-theory time-complexity space-complexity gdiazc
sumber

Saya kira ada mult. konstanta bersembunyi di sana. Anda dapat membuktikan bahwa

. Cukup sebutkan semua dugaan non-deterministik dari algoritma, dan jalankan algoritma Anda dengan tebakan ini. Terima jika salah satu tebakan mengarah ke kondisi penerimaan.

N T I M E (f (n)) \subseteq D S P A C E (2 \cdot f (n))

$NTIME(f(n)) \subseteq DSPACE(2\cdot f(n))$

Igor Shinkar

Mengapa tidak membuat ini jawaban?

Yuval Filmus

@IgorShinkar Ada berbagai hasil, seperti teorema speedup linier dan teorema kompresi kaset yang mengatakan Anda dapat menyingkirkan konstanta tersebut dalam keadaan "kebanyakan". Linear speedup mengatakan bahwa

untuk

; kompresi kaset mengatakan bahwa

D T I M E (f (n)) \subseteq D T I M E (ϵ f (n) + n + 2)

$\mathrm{DTIME}(f(n)) \subseteq \mathrm{DTIME}(\epsilon f(n)+n+2)$

ϵ > 0

$\epsilon>0$

, lagi untuk setiap

D S P A C E (f (n)) \subseteq D S P A C E (ϵ f (n) + O (1))

$\mathrm{DSPACE}(f(n))\subseteq \mathrm{DSPACE}(\epsilon f(n) + O(1))$

ϵ > 0

$\epsilon>0$

David Richerby

Jawaban:

Ini adalah versi yang diperluas dari komentar Igor Shinkar. Cara paling sederhana untuk mensimulasikan mesin non-deterministik berjalan dalam waktu dan spasi menggunakan ruang . Kami menghitung semua kemungkinan lemparan koin, mensimulasikan mesin asli pada masing-masing; ini membutuhkan ruang untuk menyimpan lemparan koin, dan $f(n)$ $s(n) \leq f(n)$ $s(n) + 2f(n) + O(1)$ $f(n)$ ruang untuk mensimulasikan mesin yang sebenarnya. Ada sedikit kesulitan di sini: ketika lemparan koin "dibaca" oleh mesin (asli), kita perlu menandai di mana pun kita berada dalam urutan lemparan koin; kita bisa menggunakan bit tambahan per lemparan koin. Mungkin dimungkinkan untuk mengoptimalkan ini lebih jauh. $s(n)$

Jika kita berhati-hati, kita mungkin bisa mendapatkan sesuatu yang lebih baik, karena dalam setiap menjalankan program, jumlah total lemparan koin dan total ruang yang digunakan menambah paling banyak untuk . Saya menduga mungkin untuk menjalankan simulasi di $f(n)$ ruang. Mungkin kita perlu mengasumsikan sesuatu seperti untuk itu. $(1+o(1))f(n)$ $f(n) = \Omega(\log n)$

Seperti yang disebutkan Igor, biasanya kelas yang dibatasi sumber daya hanya didefinisikan "hingga O besar", sehingga hasilnya, yang menggunakan ruang , masih dalam . $O(f(n))$ $\mathrm{DSPACE}(f(n))$

Yuval Filmus
sumber