Apa oracle kompleksitas minimum yang memisahkan PSPACE dari hierarki polinomial?

Latar Belakang

Hal ini diketahui bahwa ada sebuah ramalan $A$ seperti itu, $PSPACE^A \neq PH^A$ .

Bahkan diketahui bahwa pemisahan relatif terhadap oracle acak. Secara informal, seseorang mungkin menafsirkan ini berarti bahwa ada banyak nubuat yang $PSPACE$ dan $PH$ terpisah.

Pertanyaan

Bagaimana rumit adalah firman ini yang memisahkan $PSPACE$ dari $PH$ . Secara khusus, apakah ada oracle $A \in DTIME(2^{2^{n}})$ sedemikian rupa sehingga $PSPACE^A \neq PH^A$ ?

Apakah kita memiliki oracle $A$ sehingga $PSPACE^A \neq PH^A$ dan $A$ memiliki kompleksitas yang diketahui batas atas?

Catatan: keberadaan oracle semacam itu mungkin memiliki konsekuensi dalam teori kompleksitas struktural. Lihat pembaruan berikut di bawah ini untuk perincian lebih lanjut.

Perbarui dengan detail tentang teknik batas bawah

Klaim: Jika $PSPACE = PH$ , maka untuk semua nubuat $A \in P/poly$ , $PSPACE^A = PH^A$ .

Bukti Sketch: Misalkan $PSPACE = PH$ .

Biarkan oracle $A \in P/poly$ diberikan. Kita dapat membangun waktu polinomial $\Sigma_2$ mesin Turing oracle $M$ yang untuk panjang tertentu $n$ , menebak rangkaian ukuran $p(n)$ menggunakan kuantifikasi eksistensial dan memverifikasi bahwa rangkaian memutuskan $A$ dengan membandingkan evaluasi rangkaian dan hasil kueri untuk setiap panjang $n$ string menggunakan kuantifikasi universal.

Selanjutnya, pertimbangkan masalah keputusan yang saya sebut sebagai sirkuit Boolean terukur (QBC) di mana Anda diberi sirkuit boolean terukur dan ingin tahu apakah itu valid (mirip dengan QBF). Masalah ini selesai PSPACE karena QBF selesai PSPACE.

Dengan asumsi, berikut bahwa QBC . Katakanlah Q B C ∈ Σ k untuk beberapa k cukup besar. Misalkan N menunjukkan waktu polinomial Σ k Mesin Turing yang memecahkan QBC.$\in PH$$QBC \in \Sigma_k$$k$$N$$\Sigma_k$

Kita bisa berbaur perhitungan dan N (mirip dengan apa yang dilakukan dalam bukti teorema Karp-Lipton) untuk mendapatkan waktu polinomial Σ k mesin oracle Turing yang memecahkan Q B C A .$M$$N$$\Sigma_k$$QBC^A$

Secara informal, mesin baru ini mengambil input QBC oracle (yaitu QBC dengan gerbang oracle). Kemudian, ia menghitung sirkuit yang menghitung pada input dengan panjang n (secara bersamaan melepaskan dua bilangan pertama). Berikutnya, menggantikan gerbang oracle di QBC oracle dengan sirkuit untuk A . Akhirnya, ia mulai menerapkan sisa algoritma waktu polinomial Σ k untuk menyelesaikan Q B C pada contoh yang dimodifikasi ini.$A$$n$$A$$\Sigma_k$$QBC$

Sekarang, kita dapat menunjukkan batas bawah bersyarat.

Konsekuensi: Jika ada oracle sedemikian rupa sehingga P S P A C E A ≠ P H A , maka N E X P ⊈ P / p o l y .$A \in NEXP$$PSPACE^A \neq PH^A$$NEXP \nsubseteq P/poly$

Bukti Sketch: Misalkan terdapat sehingga P S P A C E A ≠ P H A . Jika N E X P ⊆ P / p o l y , maka kita akan mendapat kontradiksi.$A \in NEXP$$PSPACE^A \neq PH^A$$NEXP \subseteq P/poly$

Secara khusus, jika , maka dengan klaim atas kita memiliki P S P A C E ≠ P H . Namun, diketahui bahwa N E X P ⊆ P / p o l y menyiratkan bahwa P S P A C E = P H .$NEXP \subseteq P/poly$$PSPACE \neq PH$$NEXP \subseteq P/poly$$PSPACE = PH$

(lihat di sini untuk beberapa detail tentang hasil yang diketahui untuk P / poli)

Saya percaya jika Anda menelusuri argumen yang diberikan, misalnya, dalam Bagian 4.1 dari survei Ker-I Ko , Anda mendapatkan batas atas . Bahkan, kita dapat mengganti n 2 di sini dengan fungsi apa pun n f ( n ) di mana f $\mathsf{DTIME}(2^{2^{O(n^2)}})$$n^2$$nf(n)$ sebagai n → ∞ . Ini tidak cukup apa yang diminta, tetapi sudah dekat.$f(n) \to \infty$$n \to \infty$

Secara khusus, menggunakan terjemahan antara pemisahan oracle dan sirkuit batas bawah, dan mengikuti notasi Ko, kami memiliki yang berikut:

• Kami akan mendiagonalisasi string panjang mana p n ( x ) = x n + n adalah " polinomial ke- n (dalam beberapa enumerasi algoritma poli-waktu) dan m ( n ) akan ditentukan di bawah ini.$t(n) = p_n(m(n))$$p_n(x) = x^n + n$$n$$m(n)$

• Menerjemahkan ke batas bawah sirkuit, ini berarti kami sedang mempertimbangkan sirkuit dengan kedalaman terbatas pada input.$2^{t(n)}$

• Persyaratan (lihat hlm. 15 dari Ko) yang kita butuhkan untuk memenuhi $m(n)$untuk semuan. Berikutdadalah kedalaman sirkuit kita ingin diagonalize terhadap, atau ekuivalen tingkatΣ p d dariPHkita ingin diagonalize melawan. Untuk diagonalize terhadap semuaPH, silahkandmenjadi fungsi dari$\frac{1}{10} 2^{m/(d-1)} > d p_n(m(n))$$n$$d$$\mathsf{\Sigma_d^p}$$\mathsf{PH}$$\mathsf{PH}$$d$$n$ yang ; kita dapat memilih a $\omega(1)$$d$yang tumbuh secara sewenang-wenang perlahan-lahan, meskipun (mungkin tunduk pada beberapa asumsi komputabilitas pada , tetapi itu seharusnya tidak menjadi hambatan). Jika kita membuat dugaan bahwa d ( n ) adalah konstan (walaupun tidak, tetapi akan tumbuh secara lambat), maka kita melihat bahwa m ( n ) sekitar 2 n harus bekerja.$d(n)$$d(n)$$m(n)$$2^n$

• Ini berarti bahwa , jadi kami mencari batas bawah terhadap rangkaian dengan ∼ 2 2 n 2 input.$t(n) \sim 2^{n^2}$$\sim 2^{2^{n^2}}$

• Trevisan dan Xue (CCC '13) menunjukkan bahwa seseorang dapat menemukan tugas di mana rangkaian batas-terikat yang diberikan pada input tidak menghitung PARITY dengan seed panjang p o l y l o g ( N ) .$N$$polylog(N)$

• Bagi kami , jadi p o l y l o g ( N ) = 2 O ( n 2 ) . Kita dapat dengan kasar memaksakan benih seperti itu dalam 2 2 O ( n 2 ) waktu dan menggunakan yang pertama yang berfungsi.$N=2^{2^{n^2}}$$polylog(N) = 2^{O(n^2)}$$2^{2^{O(n^2)}}$

Untuk mengganti dengan n f ( n ) , biarkan saja p n ( x ) = x f ( $n^2$$nf(n)$sebagai gantinya.$p_n(x) = x^{f(n)} + f(n)$

Menariknya, jika saya mengerti dengan benar, saya percaya ini menyiratkan bahwa jika seseorang dapat meningkatkan Trevisan-Xue ...

• ... untuk algoritma pseudodeterministic / Bellagio (lihat komentar Andrew Morgan di bawah), orang akan mendapatkan bahwa ; atau$\mathsf{BPEXP} \not\subseteq \mathsf{P/poly}$

• ... untuk algoritma non-deterministik yang menduga bit tapi kemudian berlari di p o l y ( N ) waktu, dan sehingga pada setiap jalur menerimanya membuat output yang sama ( lih N P S V ), itu akan menyiratkan N E X P ⊈ P / p o l y ; atau$polylog(N)$$poly(N)$$\mathsf{NPSV}$$\mathsf{NEXP} \not\subseteq \mathsf{P/poly}$

• ... ke algoritma deterministik, orang akan mendapatkan .$\mathsf{EXP} \not\subseteq \mathsf{P/poly}$

Di satu sisi, ini menunjukkan mengapa derandomisasi lemma pengalihan lebih lanjut harus sulit - argumen yang saya tidak yakin dikenal sebelumnya! Di sisi lain, ini menurut saya hal yang menarik tentang kekerasan versus keacakan (atau apakah ini benar-benar hal baru, ramalan versus keacakan?).