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

12

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 DTISP(g(n),O(s(n))) terkait dengan DTISP(f(n),O(s(n))) jika fg tumbuh cukup cepat?

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

Secara khusus, saya dianggap berikut bahasa: Lk:={(M,w):M rejects (M,w) using at most |M,w|3 time steps, k|M,w| cells and four different tape symbols}

Namun, Lk bisa diputuskan dalam n3 langkah dengan menggunakan (k+1)nO(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 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 DSPACE(s(n))DTIME(f(n)) menjadi DTISP(f(n),s(n)) , namun, saya pikir persimpangan juga layak untuk dipikirkan.

Henning
sumber
Pertanyaan yang luar biasa !! Juga cukup menarik untuk melihat DTISP (g (n), s (n)) vs DTISP (f (n), s (n)) jika tumbuh cukup cepat. DTISP (g (n), s (n)) mewakili bahasa yang dapat diselesaikan dengan algoritma tunggal yang berjalan paling banyak pada waktu g (n) menggunakan ruang s (n) sementara DTIME (g (n))DSPACE (s (n)) mewakili bahasa dengan dua algoritma di mana satu algoritma berjalan dalam waktu g (n) dan algoritma lainnya berjalan dalam ruang s (n). fg
Michael Wehar
1
Ups ... Saya benar-benar menulis D-SPACE (O (s (n))) - TIME (g (n)) pertama, tapi saya tidak suka tampilan apa yang dibuat MathJax dari itu, jadi saya segera mengubahnya ke DSPACE (O (s (n))) ∩ DTIME (g (n)) tanpa banyak berpikir tentang hal itu. Pertanyaan awal saya adalah tentang apa yang saya tulis pertama, tetapi persimpangan DSPACE (O (s (n))) ∩ DTIME (g (n)) juga sangat menarik - Saya senang saya melakukan kesalahan ini. Jelas DTISP (g (n), s (n)) ⊆ DTIME (g (n)) ∩ DSPACE (s (n)). Apakah ini inklusi yang tepat? Menurut wikipedia, kelayakannya tidak diketahui untuk DTISP (P, PolyL) ⊆ DTIME (P) ∩ DSPACE (PolyL): wikiwand.com/en/SC_(complexity)
Henning
Keren!! Terimakasih atas klarifikasi Anda. Saya sangat tertarik dengan masalah seperti ini. :)
Michael Wehar
. Jadi, kasus kedua Anda sepele. DTISP(2n,n)=DSPACE(n)
rus9384
Perlu disebutkan bahwa hierarki waktu untuk jumlah ruang tetap dapat diperoleh untuk mesin Turing dengan kaset untuk fix k dengan menggunakan argumen yang mirip dengan Hopcroft-Paul-Valiant dan hierarki waktu ketat untuk mesin k -tape. Lihat misalnya WJ Paul. `Tepat waktu hierarki 'dalam STOC'77kkk
Sam McGuire

Jawaban:

5

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 )DTISP(O(nlogn),O(n))=DSPACE(O(n))NSPACE(O(n)) .DTIME(O(n))DSPACE(O(n/logn))

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.ε>0O(2nε)DTISP(O(f),O(s(n)))DTISP(O(f1+ε),O(s(n)))
f(n)nf(n)2o(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.lg(f1+ε/2)(logf)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 .nnO(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 ).ff(n)=na

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

  • Untuk membedakan dari , kita hanya perlu asumsi P ≠ PSPACE yang lebih lemah.na2n

Dmytro Taranovsky
sumber