Jika kita melihat teorema hierarki DTIME, kita punya log karena overhead dalam simulasi Mesin Turing deterministik oleh mesin universal:
Kami belum memiliki overhead semacam ini untuk NTIME dari DSPACE. Pembenaran dasar berasal dari rincian bukti dengan mempertimbangkan perbedaan antara simulator.
Pertanyaan saya adalah sebagai berikut: tanpa mempertimbangkan perincian bukti teorema hierarki DTIME, apakah ada pembenaran dari log ini atau itu bisa menjadi konsekuensi dari buktinya dan masuk akal untuk membayangkan bahwa jika kemudian
Menurut pendapat saya, mengingat bahwa penjelasan simulasi adalah pembenaran yang baik harus dibenarkan dengan membuktikan bahwa jika kita memiliki hasil yang lebih baik, maka kita dapat membuat simulasi yang lebih baik.
sumber
Jawaban:
Teorema hierarki waktu adalah subjek dari proyek diploma saya, mungkin Anda ingin melihat komentar pada pertanyaan saya Batas bawah dan pemisahan kelas .
Melihat kembali ke pertanyaan ini dan bagaimana hubungannya dengan apa yang Anda tanyakan, saya mendapat ide yang mungkin menunjukkan bahwa multitape untuk single tape TM simulasi yang diperlukan oleh bukti teorema tidak dapat diperbaiki. Maka, pendekatan lain diperlukan jika kita ingin meningkatkan hasil ini.
EDIT: Bukti ini salah, lihat komentar di bawah untuk alasan yang tepat. Saat ini saya sedang mengedit jawaban untuk mencerminkan itu.
Biarkan menjadi bahasa { 0 k 1 k | k ≥ 0 } .A {0k1k|k≥0}
Pada mesin tape tunggal, ada algoritma (Anda dapat menemukan detail dari algoritma ini dalam bab 7.1.2 dari buku Sipser "Pengantar Teori Komputasi). Dalam referensi yang sama, Anda dapat melihat bahwa bahasa dalam o (n \ log n) jika dan hanya jika itu adalah biasa. Kaveh juga menyediakan makalah asli untuk klaim ini dalam pertanyaan yang ditautkan di atas.O(nlogn)
Dalam komentar pertanyaan saya, Ryan Williams menggambarkan algoritma untuk masalah yang sama, menggunakan 2-tape TM.O(n)
Asumsikan sekarang bahwa ada teknik untuk mensimulasikan multitape TM ke dalam single tape TM yang memiliki waktu berjalan , di mana adalah waktu berjalan dari simulasi TM . Dengan menerapkannya pada mesin yang diilustrasikan Ryan, kita akan mendapatkan satu kaset TM yang akan berjalan di . Oleh karena itu, adalah reguler, yang merupakan kontradiksi. Jadi, kami menyimpulkan bahwa overhead adalah yang terbaik yang bisa kami lakukan ketika mensimulasikan mesin multi tape dengan mesin single tape.T ( n ) o ( n logo(T(n)logT(n)) T(n) o(nlogn) log T ( n )A logT(n)
Saya menyadari ini adalah pernyataan yang kuat, jadi saya mungkin salah dalam penafsiran saya.
Bahkan jika ada teknik yang memungkinkan untuk meningkatkan hasil ini, saya percaya bahwa tidak mungkin untuk mencocokkan hasil untuk atau . Intuisi saya berasal dari fakta berikut:S P A C ENTIME SPACE
Ada hasil yang sangat dikenal yang menyatakan . Dengan asumsi bahwa Saya percaya hasil ini ditingkatkan menjadi , untuk setiap . Jadi, kelas non-deterministik yang sangat kecil jauh lebih kuat daripada deterministik apa pun. . Jadi, mengingat seberapa kuat waktu non-deterministik sumber daya, saya berharap bahwa jumlah waktu deterministik yang lebih besar akan diperlukan untuk membuat TM lebih kuat untuk mengimbangi kekuatan non-determinisme.DTIME(n)≠NTIME(n) P≠NP DTIME(nk)≠NTIME(n) k
sumber
Untuk n-tape TM, hasil hierarki waktu yang ketat mirip dengan teorema hierarki ruang dibuktikan oleh Furer pada tahun 1982. Faktor tidak diperlukan.lg
The faktor untuk teorema waktu hirarki dinyatakan dalam posting Anda hanya untuk TM single-tape. Kecuali jika Anda sangat berkomitmen pada model pita tunggal karena alasan tertentu, tidak ada perbedaan antara ruang dan waktu mengenai teorema hierarki.lg
Ada beberapa alasan dan argumen untuk menggunakan TM single-tape untuk mendefinisikan kelas kompleksitas waktu, tetapi penggunaan single-tape TM untuk mendefinisikan kelas kompleksitas tidak universal, misalnya lihat Lance Fortnow dan Rahul Santhanam [2007] di mana mereka menggunakan multi-tape TMs.
Referensi asli untuk teorema hierarki waktu adalah Hennie dan Stearns [1966]. Mereka membuktikan teorema untuk mesin dua-pita. Teori Rekursi Klasik Odifreddi mengutip mereka dan Hartmanis [1968] dan menjelaskan bukti yang terlihat mirip dengan yang ada di buku Sipser.
Namun bukti untuk TM pita tunggal dalam kertas Hartmanis tidak menggunakan simulasi sederhana. Ini membedakan antara dua kasus: 1. waktu berjalan dan 2. waktu berjalan sedang o ( n 2 ) .Ω(n2) o ( n2)
Untuk kasus pertama menggunakan simulasi, dan tampaknya seseorang dapat menghilangkan faktor jika simulasi dapat dilakukan dengan lebih efisien.lg
Untuk kasus kedua, makalah ini secara langsung memberikan bahasa untuk pemisahan dan tidak menggunakan simulasi sama sekali. Ini menggunakan sifat-sifat tertentu dari TM single-tape dengan waktu berjalan sub-kuadratik.
Kita harus mencatat bahwa TM single-tape dengan waktu tidak sekuat dan ada lowerbound kuadratik (misalnya untuk Palindrom) pada TM single-tape sedangkan TM dua-tape dapat menyelesaikan masalah seperti itu dalam waktu linier.o ( n2)
Seperti yang saya katakan di atas, kecuali Anda berkomitmen untuk model single-tape TM karena alasan tertentu, bahkan ketika waktu sub-kuadrat, tidak ada celah untuk diisi, teorema hierarki waktu seketat mungkin.
PS: jika kita menggunakan TM multi-tape, yaitu mesin Turing di kelas dapat memperbaikinya tetapi jumlah kaset yang berubah-ubah, hasil Fürer tidak berlaku.
sumber
Untuk jumlah kaset yang lebih besar dari satu, ) untuk konstruk waktu f . Overhead logaritmik berasal dari teorema pengurangan pita, di mana sejumlah kaset dapat dikonversi menjadi dua kaset (atau bahkan hanya satu kaset dan tumpukan dan dengan hanya gerakan yang tidak sadar).T i m e (o(f) ) ⊊ T i m e ( O ( f) f
Jika jumlah kaset tidak tetap, kami tidak benar-benar memiliki teknik untuk secara konstruktif membuktikan tanpa melalui teorema pengurangan kaset. Adalah masuk akal bahwa untuk setiap mesin k , k + 1 -tape tidak dapat disimulasikan oleh mesin k -tape tanpa overhead logaritmik.D T i m e (g) ⊊ D T i m e ( f) k k + 1 k
Namun, itu tidak berarti teorema hierarki waktu tidak dapat ditingkatkan, atau bahwa gagal.DTime(o(f))⊊DTime(O(f))
Sebenarnya, kami sudah memiliki yang berikut ini.
Teorema: Untuk setiap dan setiap f dari bentuk n a ( log n ) b ( a dan b rasional; a > 1 atau a = 1 ∧ b ≥ 0 ), D T i m e ( O ( f / ( log f ) ε ) ⊊ε>0 f na(logn)b a b a>1 a=1∧b≥0 .DTime(O(f/(logf)ε)⊊DTime(O(f))
Bukti: Jika setiap bahasa dengan algoritma keputusan dapat diputuskan dalam waktu O ( f / ( log f ) ε ) , maka dengan mengisi input, setiap bahasa dengan O ( f ( n ) ( log f ( n) ) ) k ε )O(f) O(f/(logf)ε) O(f(n)(logf(n))kε) algoritma keputusan dapat diputuskan dalam waktu (di mana k ≥ 0 ditetapkan), dan untuk setiap konstanta c ≥ 0 , D T i m e ( O ( f ( n )) ( log f ( n ) ) c ) ) = D T i m e ( O ( f ( nO(f(n)(logf(n))(k−1)ε) k≥0 c≥0 , bertentangan dengan teorema hierarki waktu.DTime(O(f(n)(logf(n))c))=DTime(O(f(n)))
Namun, bukti non-konstruktif ini memiliki tiga batasan:f
DTime(O(f)) DTime(O(f/(logf)ε) k k , tetapi kami belum mengesampingkan bahwa bahkan untuk ε = 1 dan f ( n ) = n 2 , k yang paling sedikitadalah> BB (BB (1000)) di mana BB adalah fungsi berang-berang yang sibuk.
* Kita tidak tahu bahwa penyertaannya kuat. A D T i m e ( O ( f / ( log f ) ε )DTime(O(f/(logf)ε) ε=1 f(n)=n2 k
DTime(O(f/(logf)ε) Algoritme akan gagal untuk beberapa input, tetapi kami belum membuktikan bahwa itu gagal untuk beberapa input untuk semua ukuran input tetapi banyak (meskipun akan sangat mengejutkan jika tidak).
* Bukti tersebut menuntut untuk berperilaku baik (tidak hanya konstruktif waktu, tetapi juga dalam arti tertentu terus menerus). * Kita tidak tahu bahasa tertentu yang ada dalam D T i m e ( O ( f ) ) tetapi tidak dalam D T i m e ( O ( f / ( log f ) ε ) . Untuk k yang cukup besar , simulasi dari k -tape Mesin Turing tidak dalam D
sumber