Hierarki untuk BPP vs derandomisasi

Dalam satu kalimat: apakah akan ada hierarki untuk menyiratkan hasil derandomisasi?$\mathsf{BPTIME}$

Pertanyaan yang terkait tetapi tidak jelas adalah: apakah keberadaan hierarki untuk menyiratkan adanya batas bawah yang sulit? Apakah resolusi masalah ini menabrak penghalang yang dikenal dalam teori kompleksitas?$\mathsf{BPTIME}$

Motivasi saya untuk pertanyaan ini adalah untuk memahami kesulitan relatif (sehubungan dengan masalah terbuka utama lainnya dalam teori kompleksitas) untuk menunjukkan hierarki untuk . Saya berasumsi bahwa semua orang percaya bahwa hierarki seperti itu ada, tetapi tolong perbaiki saya jika Anda berpikir sebaliknya.$\mathsf{BPTIME}$

Beberapa latar belakang : berisi bahasa-bahasa yang keanggotaannya dapat ditentukan oleh mesin Turning probabilistik dalam waktu dengan probabilitas kesalahan terbatas. Lebih tepatnya, bahasa jika ada mesin Turing probabilistik sedemikian rupa sehingga untuk setiap mesin berjalan dalam waktu dan menerima dengan probabilitas setidaknya , dan untuk setiap , berjalan dalam waktu dan menolak dengan probabilitas setidaknya .$\mathsf{BPTIME}(f(n))$$f(n)$$L \in \mathsf{BPTIME}(f(n))$$T$$x \in L$$T$$O(f(|x|))$$2/3$$x \not \in L$$T$$O(f(|x|))$$2/3$

Tanpa syarat, terbuka apakah untuk semua . Barak menunjukkan bahwa ada hierarki yang ketat untuk untuk mesin dengan saran . Fortnow dan Santhanam meningkatkan ini menjadi 1 saran. Hal ini membuat saya berpikir bahwa membuktikan keberadaan hierarki waktu probabilistik tidak terlalu jauh. Di sisi lain, hasilnya masih terbuka dan saya tidak dapat menemukan kemajuan setelah 2004. Referensi, seperti biasa, dapat ditemukan di Kebun Binatang .$\mathsf{BPTIME}(n^c) \subseteq \mathsf{BPTIME}(n)$$c > 1$$\mathsf{BPTIME}$$O(\log n)$

Hubungan dengan derandomisasi berasal dari hasil Impagliazzo dan Wigderson: mereka menunjukkan bahwa di bawah asumsi kompleksitas yang masuk akal, untuk konstanta dan beberapa konstanta . Dengan teorema hierarki-waktu klasik untuk waktu deterministik, ini menyiratkan hierarki waktu untuk waktu probabilistik. Saya mengajukan pertanyaan sebaliknya: apakah hiearchy probabilistik menabrak penghalang terkait dengan membuktikan hasil derandomisasi?$\mathsf{BPTIME}(n^d) \subseteq \mathsf{DTIME}(n^c)$$d$$c$

Jika ada yang memiliki pengamatan tentang apa yang berdiri di antara kita dan membuktikan keberadaan hierarki untuk waktu probabilistik, jangan ragu untuk menjawab / berkomentar. Tentu saja, jawaban yang jelas adalah bahwa memiliki definisi semantik yang menentang teknik klasik. Saya tertarik pada pengamatan yang kurang jelas.$\mathsf{BPTIME}$

Biarkan PTH menjadi hipotesis bahwa ada hierarki waktu probabilistik. Misalkan jawaban untuk pertanyaan Anda adalah benar, yaitu, "PTH menyiratkan " untuk beberapa . Kemudian, akan benar tanpa syarat. Pertimbangkan dua kasus:$BPP \subseteq TIME[2^{n^{c}}]$$c$$EXP \neq BPP$

• Jika PTH salah, maka . Ini adalah alat kontras dari apa yang dicatat Lance.$EXP \neq BPP$
• Jika PTH benar, maka "PTH menyiratkan " jadi .$BPP \subseteq TIME[2^{n^{c}}]$$EXP \neq BPP$

Faktanya, bahkan derandomisasi BPP yang tak terhingga-sering di bawah PTH akan memerlukan tanpa syarat. Jadi, apa pun hambatan yang berlaku untuk membuktikan , mereka berlaku untuk membuktikan pernyataan dari jenis "PTH menyiratkan derandomisasi".$EXP \neq BPP$$EXP \neq BPP$

Tidak sulit untuk memperoleh hierarki waktu probabilistik jika BPP = EXP, kasus ekstrem dari tidak ada derandomisasi.