Apakah perhitungan nondeterminisme kuadrat mempercepat perhitungan deterministik masuk akal?

9

Ini adalah tindak lanjut dari perhitungan deterministik yang tidak deterministik .

Apakah masuk akal bahwa nondeterminisme (atau lebih umum pergantian) akan memungkinkan percepatan kuadratik umum dari perhitungan deterministik? Atau adakah konsekuensi tidak masuk akal yang diketahui untuk sesuatu seperti ?DTime(n2)NTime(n)

Kaveh
sumber
Saya tidak yakin tapi saya pikir dengan argumen yang sama yang digunakan dalam pertanyaan Anda sebelumnya kita memiliki tidak dalam D T I M E ( n 2 / lg n ) . Sebenarnya T M S A T tidak ada dalam D T I M E ( n ) , karena N T I M E ( n ) D T I M E ( n ) , tetapi saya tidak tahu batas bawah yang lebih baik.
TMSAT={<a,x,1n,1t>:u{0,1}ns.t.Maoutputs1oninput<x,u>withintsteps}
DTIME(n2/lgn)TMSATDTIME(n)NTIME(n)DTIME(n)
Erfan Khaniki
@ Erfan, argumen saya tidak menunjukkan itu tidak, itu juga tidak menunjukkan bahwa itu tidak mungkin, itu hanya menunjukkan bahwa membuktikan bahwa itu tidak diketahui dan sulit untuk . ω(nlgn)2
Kaveh
Ya kamu benar. Sebenarnya argumen ini menunjukkan bahwa sulit untuk membuktikan . DTIME(n2)NTIME(n)
Erfan Khaniki

Jawaban:

10

DTime(O~(n2))NTime(n2ϵ)O~(n2)

Joe Bebel
sumber