Percepatan deterministik yang tidak deterministik

Bisakah nondeterminisme mempercepat perhitungan deterministik? Jika ya, berapa banyak?

Dengan mempercepat perhitungan deterministik dengan nondeterminisme yang saya maksud adalah hasil dari bentuk:

$\mathsf{DTime}(f(n)) \subseteq \mathsf{NTime}(n)$

Misalnya sesuatu

$\mathsf{DTime}(n^2) \subseteq \mathsf{NTime}(n)$

Apa hasil percepatan yang paling dikenal dari perhitungan deterministik oleh nondeterminisme? Bagaimana dengan atau bahkan menggantikan ? $\mathsf{\Sigma^P_kTime}(n)$ $\mathsf{ATime}(n)$ $\mathsf{NTime}(n)$

Asumsikan bahwa kelas kompleksitas didefinisikan menggunakan mesin Turing multi-tape untuk menghindari kekhasan yang diketahui dari mesin Turing single-tape sub-kuadratik.

cc.complexity-theory nondeterminism speed-up alternation tradeoff Kaveh
sumber

(Dengan Teorema 4.1 dan Waktu Hierarchy Teorema, misalnya Anda tidak dapat tahan selama TM 1-tape.)

Jawaban:

Anda seharusnya tidak mengharapkan peningkatan yang menarik. Kita punya

D T I M E (f (n)) \subseteq N T saya M. E (f (n)) \subseteq SEBUAH T saya M. E (f (n)) \subseteq D S P SEBUAH C E (f (n)),

$\mathrm{DTIME}(f(n))\subseteq\mathrm{NTIME}(f(n))\subseteq\mathrm{ATIME}(f(n))\subseteq\mathrm{DSPACE}(f(n)),$

dan simulasi waktu deterministik oleh ruang angkasa yang paling dikenal masih merupakan teorema Hopcroft-Paul-Valiant

D T I M E (f (n)) \subseteq D S P A C E (f (n) / \log f (n)) .

$\mathrm{DTIME}(f(n))\subseteq\mathrm{DSPACE}(f(n)/\log f(n)).$

Dengan demikian, nondeterminisme atau pergantian tidak diketahui memberi kecepatan lebih dari faktor logaritmik. (Saya menduga tidak ada super-linear speed-up yang diketahui, meskipun saya tidak yakin apakah teorema HPV tidak dapat dibuat untuk bekerja dengan ATIME menggantikan DSPACE.)

Emil Jeřábek mendukung Monica
sumber

Untuk mesin Turing daring satu-pita, adalah cerita rakyat bahwa

N T I M E (n) \subseteq D S P A C E (\sqrt{n})

$NTIME(n) \subseteq DSPACE(\sqrt{n})$

Michael Wehar

Untuk mesin Turing dua pita, kami memiliki

seperti yang dinyatakan di atas.

D T I M E (n) \subseteq D S P A C E (n / \log (n))

$DTIME(n) \subseteq DSPACE(n/\log(n))$

Michael Wehar

Pertanyaannya adalah tentang mesin Turing multitape.

Emil Jeřábek mendukung Monica

Saya hanya ingin memberikan klarifikasi tambahan untuk pembaca yang tertarik.

Michael Wehar

Oleh Paul-Pippenger-Szemerédi-Trotter, penyertaan pertama adalah

untuk kasus khusus di mana

DTIME (f (n)) ⊊ NTIME (f (n))

$\text{DTIME}(f(n)) \subsetneq \text{NTIME}(f(n))$

f (n) = n

$f(n)=n$

András Salamon

Ada dua konsep berbeda:

(1) Simulasi mesin deterministik yang efisien oleh mesin non-deterministik.

(2) Mempercepat hasil yang diperoleh dengan menerapkan simulasi berulang-ulang.

Saya tidak tahu ada simulasi efisien mesin deterministik oleh yang non-deterministik, tetapi saya tahu beberapa hasil percepatan yang dapat digunakan jika simulasi efisien ada.

Pertimbangkan kelas bahasa yang dapat ditentukan oleh mesin Turing non-deterministik yang berjalan selama waktu hanya menggunakan tebakan non-deterministik. Dengan kata lain, panjang saksi dibatasi oleh . $NTIGU(t(n), g(n))$ $t(n)$ $g(n)$ $g(n)$

Jika Anda memiliki simulasi lebih efisien hanya menggunakan dugaan non-deterministik, maka saya percaya Anda bisa mempercepatnya cukup sedikit. Secara khusus, saya yakin Anda dapat membuktikan hal berikut: $\log(n)$

Jika , maka $DTIME(n \log(n)) \subseteq NTIGU(n, \log(n))$ . $DTIME(2^{\sqrt{n}}) \subseteq NTIME(n)$

Jika Anda menemukan ini menarik, maka saya bisa menulis buktinya.

Ryan Williams memperkenalkan beberapa peningkatan terkait dalam "Meningkatkan Pencarian Lengkap Mengimplikasikan Batas Bawah Superpolinomial".

Michael Wehar
sumber

Seperti yang Anda lihat,

adalah asumsi yang agak besar dan cukup masuk akal bahwa Anda dapat membuktikan hipotesis itu salah. . Beri tahu saya jika Anda melakukannya. :)

D T I M E (n \log (n)) \subseteq N T I G U (n, \log (n))

$DTIME(n \log(n)) \subseteq NTIGU(n, \log(n))$

Michael Wehar

@AndrasSalamon: Bagaimana cara

mengikuti dari pencarian lengkap?

\subseteq

$\subseteq$

@ RickyDemer Anda benar, itu tidak; telah menghapus komentar. Secara implisit saya berasumsi bahwa nondeterminisme berada di akhir perhitungan, tetapi harus diasumsikan sebagai permulaan.

András Salamon

Pembaruan: Akhirnya mulai menulis hasil percepatan yang diusulkan yang saya sebutkan. Tampaknya sedikit berbeda dari hasil mempercepat lainnya yang saya temukan. Silakan membalas atau mengirim email kepada saya jika Anda tertarik untuk berdiskusi. Terima kasih! :)

Michael Wehar

pasti akan melihatnya, ini adalah pendekatan yang menarik.

András Salamon

Berikut ini adalah penjelasan mengapa kecepatan quartic nondeterministic umum dari perhitungan deterministik bahkan jika benar akan sulit untuk dibuktikan:

Asumsikan bahwa kecepatan quartic nondeterministic umum dari perhitungan deterministik seperti berlaku. Demi kontradiksi, asumsikan bahwa . Ada pengurangan waktu kuadratik dari masalah apa pun di $\mathsf{DTime}(n^4) \subseteq \mathsf{NTime}(n)$ $\mathsf{SAT} \in \mathsf{DTime}(o(n^2/\lg n))$ Untuk . Menggabungkan ini kita akan memiliki bertentangan dengan teorema hierarki waktu. $\mathsf{NTime}(n)$ $\mathsf{SAT}$ $\mathsf{DTime}(n^4) \subseteq \mathsf{DTime}(o(n^4/\lg n))$

Oleh karena itu, seorang jenderal quartic nonterministic kecepatan-up dari perhitungan deterministik akan berarti lebih rendah terikat untuk : $\mathsf{SAT}$

. $\mathsf{DTime}(n^4) \subseteq \mathsf{NTime}(n) \to \mathsf{SAT} \notin \mathsf{DTime}(o(n^2/\lg n))$

Oleh karena itu membuktikan umum kuadrat nondeterministic kecepatan-up dari perhitungan deterministik setidaknya sekeras membuktikan hampir kuadrat rendah-batas pada . $\mathsf{SAT}$

Demikian pula, untuk fungsi berperilaku baik : $f(n)$

. $\mathsf{DTime}(f(n^2)) \subseteq \mathsf{NTime}(n) \to \mathsf{SAT} \notin \mathsf{DTime}(o(f(n)/\lg n))$

(Jika sebagai pengganti kita memilih masalah yang sulit untuk bawah pengurangan linear-time maka ini akan memberikan batas bawah untuk masalah itu. Jika kita memperbaiki jumlah kaset mesin untuk beberapa maka kita dapat menggunakan Fürer ini waktu hirarki teorema yang tidak memiliki faktor.) $\mathsf{SAT}$ $\mathsf{NTime}(n)$ $f(n)/\lg n$ $k\geq 2$ $\lg n$

Kaveh
sumber

Karena kita bahkan tidak tahu bahwa SAT tidak dalam DTime (n), kita tidak tahu kecepatan

ω (n \lg n)^{2}

$\omega(n \lg ⁡n)^2$

Kaveh