Hierarki Waktu di DSPACE (O (s (n)))

Teorema hierarki waktu menyatakan bahwa mesin turing dapat memecahkan lebih banyak masalah jika mereka memiliki (cukup) lebih banyak waktu. Apakah itu tahan jika ruang terbatas asimptotik? Bagaimana $\textrm{DTISP}(g(n), O(s(n)))$ terkait dengan $\textrm{DTISP}(f(n), O(s(n)))$ jika $\frac{f}{g}$ tumbuh cukup cepat?

Saya terutama tertarik pada kasus yang $s(n) = n$ , $g(n) = n^3$ dan $f(n) = 2^n$ .

Secara khusus, saya dianggap berikut bahasa: $L_k := \{ (\langle M \rangle, w) \; : \; \text{M rejects } (\langle M \rangle, w) \text{ using at most } |\langle M \rangle, w|^3 \text{ time steps},$ $k * |\langle M \rangle, w| \text{ cells and four different tape symbols} \}$

Namun, $L_k$ bisa diputuskan dalam $n^3$ langkah dengan menggunakan $(k+1)n \in O(n)$ ruang.

Tanpa membatasi $M$ ke empat simbol pita dan dengan demikian memungkinkan untuk mengompresi sel-sel $O(n)$ menjadi $n$ sel, kita mendapatkan masalah ruang ketika mensimulasikan $M$ dengan terlalu banyak simbol pita. Dalam hal ini, bahasa tidak lagi dalam $\text{DSPACE}(O(n))$ . Hal yang sama terjadi ketika pengaturan $k = h(|w|)$ untuk beberapa $h$ yang dapat dihitung cukup cepat.

Pertanyaan ini pada dasarnya adalah pengulangan dari pertanyaan saya di sini .

Sunting Ringkasan: Mengubah $\textrm{DSPACE}(s(n)) \cap \textrm{DTIME}(f(n))$ menjadi $\textrm{DTISP}(f(n), s(n))$ , namun, saya pikir persimpangan juga layak untuk dipikirkan.

Ini adalah masalah terbuka: Terbuka apakah (atau bahkan N S P A C E ( O ( n ) ) ). Kita hanya tahu bahwa D T I M E ( O ( n $\mathrm{DTISP}(O(n \log n),O(n)) = \mathrm{DSPACE}(O(n))$$\mathrm{NSPACE}(O(n))$ .$\mathrm{DTIME}(O(n))⊆\mathrm{DSPACE}(O(n/\log n))$

Namun, di bawah dugaan kompleksitas komputasi yang masuk akal, ada hierarki yang tepat. Misalnya, jika untuk setiap , CIRCUIT-SAT ∉ io- , maka mana , adalah , dan adalah konstruk ruang-waktu.$ε>0$$O(2^{n-ε})$$\mathrm{DTISP}(O(f),O(s(n))) ⊊ \mathrm{DTISP}(O(f^{1+ε}),O(s(n)))$
$f(n)≥n$$f(n)$$2^{o(\min(n,s(n)))}$$f$

Khususnya (berdasarkan hipotesis), adanya penugasan yang memuaskan untuk rangkaian dengan input dan ukuran berfungsi sebagai contoh berlawanan dengan kesetaraan kelas.$⌊\mathrm{lg}(f^{1+ε/2})⌋$$(\log f)^{O(1)}$

Catatan:

• CIRCUIT-SAT setidaknya sekeras -SAT (yang digunakan dalam hipotesis waktu eksponensial yang kuat).$k$

• Per konvensi, dalam CIRCUIT-SAT, adalah jumlah kabel input; ukuran sirkuit adalah .$n$$n^{O(1)}$

• Jika asumsi menggunakan CIRCUIT-SAT untuk ukuran rangkaian quasilinear, maka ikatan pada dapat dilonggarkan ke . Juga, asumsi yang lebih lemah / kuat pada kekerasan CIRCUIT-SAT memberikan hierarki yang lebih lemah / kuat (yang saat ini dapat kita buktikan).$f(n)$$O((2-ε)^{\min(n,s(n))})$

• io berarti sering tanpa batas, dan dapat dijatuhkan untuk yang dalam arti tertentu terus menerus (termasuk ).$f$$f(n)=n^a$

• Tampaknya hierarki DTISP cukup tajam untuk membedakan dari (dan mungkin ) (ketika tidak terlalu besar relatif terhadap ruang yang diizinkan).$O(f)$$o(f/\log f)$$o(f)$$f$

• Untuk membedakan dari , kita hanya perlu asumsi P ≠ PSPACE yang lebih lemah.$n^a$$2^n$