Konsekuensi nondeterminisme mempercepat perhitungan deterministik

Jika berisi kelas masalah waktu superpolinomial, yaitu $\mathsf{NP}$

untuk beberapa fungsi , , $t \in n^{\omega(1)}$ $\mathsf{DTIME}(t) \subseteq \mathsf{NP}$

$\mathsf{P} \subsetneq \mathsf{NP}$

Tetapi apakah ada konsekuensi menarik lain yang nontrivial (yaitu bukan konsekuensi dari ) jika nondeterminisme dapat mempercepat perhitungan deterministik? $\mathsf{P} \subsetneq \mathsf{NP}$

cc.complexity-theory time-complexity nondeterminism GMB
sumber

Mohon maaf jika pertanyaan ini tidak sesuai untuk situs ini - saya akan dengan senang hati memperbaiki pertanyaannya semampu saya.

GMB

Saya pikir ini adalah pertanyaan yang menarik. Konsekuensi mudah mirip dengan pemisahan P dari NP adalah bahwa NP tidak dalam DTime (o (t) / lg n).

Kaveh

ps: Saya menghapus bagian kedua karena saya pikir itu mengganggu dan tidak menambah banyak pertanyaan.

Kaveh

Terima kasih, Kaveh - Saya sangat menghargai hasil edit! (dan dari pemilihan suara, tampaknya semua orang juga melakukannya)

GMB

Jawaban:

Saya menemukan satu konsekuensi terkait.

Katakanlah berisi , di mana . Ternyata ini hanya waktu yang cukup untuk mendiagonalisasi terhadap . Secara khusus, buat mesin berikut: $NEXP$ $DTIME(2^{O(t)})$ $t = n^{\omega(1)}$ $P/poly$

Pada masukan panjang , mempertimbangkan Turing mesin . Untuk setiap kemungkinan tali saran dari panjang dan setiap kemungkinan bitstring panjang , berjalan pada dengan nasihat , dan menolak setelah langkah jika Anda belum diterima belum. Catat hasil Anda dalam sebuah tabel. Prosedur ini berjalan dalam . $x$ $n$ $n^{th}$ $M$ $t$ $b$ $n$ $M$ $b$ $a$ $t$ $DTIME(2^{O(t)})$

Pada input , jika setidaknya setengah dari string saran menyebabkan untuk menolak, maka sebaliknya kita mendefinisikannya sebagai benar untuk algoritma kami untuk menerima (jika tidak, itu benar untuk algoritma kami untuk menolak). Setiap string saran yang menyebabkan untuk mendapatkan salah (yaitu, setidaknya setengah string saran) sekarang bisa dilemparkan keluar dari meja. Kami kemudian mengulangi proses pada input : jika setidaknya setengah dari string saran yang bertahan menyebabkan untuk menolak, maka algoritma kami akan menerima (dan menolak sebaliknya). Lanjutkan seperti ini untuk semua input panjang (walaupun sebenarnya, hanya $0^n$ $M$ $M$ $0^n$ $0^{n-1}1$ $M$ $n$ $t$ dari mereka diperlukan - setelah banyak input, kami telah membuang semua string saran yang mungkin).

Jelas bahasa ini dapat diputuskan dalam , yang kami asumsikan adalah dalam . Di sisi lain, itu tidak bisa di : himpunan panjang input mendiagonalisasi terhadap prospek yang digunakan untuk memutuskan bahasa. $DTIME(2^{O(t)})$ $NEXP$ $P/Poly$ $n$ $M_n$

Jadi kita mendapatkan , yang akan menarik. $NEXP \not \subset P/poly$

Saya akan membiarkan pertanyaan terbuka jika seseorang datang dengan sesuatu yang lain.

GMB
sumber