Lebih lanjut tentang PH dalam PP?

Sebuah pertanyaan baru - baru ini oleh Huck Bennett yang menanyakan apakah kelas PH terkandung dalam kelas PP, menerima jawaban yang agak kontradiktif (sepertinya benar). Di satu sisi, beberapa hasil oracle diberikan sebaliknya, dan di sisi lain Scott menyarankan bahwa jawabannya kemungkinan positif karena teorema Toda menunjukkan bahwa PH ada di BP.PP, varian probabilistik dari PP, dan kami biasanya percaya bahwa pengacakan tidak tidak banyak membantu, misalnya asumsi kekerasan yang masuk akal menyiratkan PRG yang dapat menggantikan pengacakan.

Sekarang, dalam kasus PP, tidak apriori jelas bahwa PRG yang "sempurna" akan menyiratkan derandomisasi lengkap karena derandomisasi alami akan menjalankan algoritma asli dengan output PRG untuk semua kemungkinan banyak polinomi-banyak dan mengambil suara mayoritas. . Tidak jelas bahwa mengambil suara terbanyak di antara perhitungan PP adalah sesuatu yang dapat dilakukan dalam PP itu sendiri. Namun, sebuah makalah oleh Fortnow dan Reingold menunjukkan bahwa PP ditutup di bawah pengurangan tabel kebenaran (memperluas hasil mengejutkan bahwa PP ditutup di bawah persimpangan), yang tampaknya cukup untuk mengambil suara mayoritas ini.

Jadi apa pertanyaannya di sini? Toda, Fortnow-Reingold dan semua derandomisasi berbasis PRG, semua tampaknya relativize, sehingga akan menyiratkan bahwa PH dalam PP untuk setiap oracle yang ada PRG yang sesuai. Jadi untuk semua nubuat di mana PP tidak mengandung PH (misalnya dari Minski & Papert, oleh Beigel , atau oleh Vereshchagin ), PRG untuk PP tidak ada. Secara khusus ini menyiratkan bahwa untuk orakel ini tidak ada fungsi keras yang sesuai dalam EXP (jika tidak, PRG seperti NW-IW akan ada). Melihat sisi positif, ini akan menyiratkan bahwa di suatu tempat di dalam masing-masing hasil oracle ini menyembunyikan algoritma PP (tidak seragam) untuk (perkiraan) EXP dengan oracle itu. Ini aneh karena semua hasil ramalan ini tampaknya bergantung pada batas bawah PP baru(untuk sirkuit ambang batas) dan lurus ke depan di mesin pembuat oracle mereka, jadi saya tidak melihat di mana batas atas untuk PP bersembunyi. Mungkin batas atas ini akan berfungsi secara umum menunjukkan bahwa (non-seragam) -PP dapat menghitung (atau setidaknya memberikan bias pada) semua EXP? Bukankah sesuatu seperti itu setidaknya memberikan simulasi CH dari EXP?

Jadi, saya kira pertanyaan saya ada dua: (1) apakah rantai penalaran ini masuk akal? (2) Jika demikian, dapatkah seseorang "mengungkap" batas atas tersirat untuk PP?

Sunting oleh Aaron Sterling: menabrak ini ke halaman depan dan menambahkan hadiah. Ini adalah salah satu pertanyaan favorit saya, dan masih belum ada jawaban.

cc.complexity-theory counting-complexity derandomization relativization Noam
sumber

Memang mulai dengan fungsi Boolean

dalam AC0 yang tidak dapat dihitung oleh gerbang ambang batas polylog (N) -degree. Untuk setiap oracle

kita mendefinisikan bahasa

(di mana

adalah

bit dari

'th sepotong

). Karena

f : {0, 1}^{N} \to {0, 1}

$f:\{0,1\}^N \rightarrow \{ 0,1\}$

A

$A$

L_{A} = {1^{n} | f (A_{n}) = 1}

$L_A= \{1^n | f(A_n)=1\}$

A_{n}

$A_n$

2^{n}

$2^n$

n

$n$

A

$A$

, untuk semua

. The

'th langkah diagonalisasi akan memilih

(untuk beberapa

) sehingga

' th PP TM membuat kesalahan pada

, yang terjadi karena

bukan ambang batas polylog (N) (seperti perhitungan mesin PP). Jadi

. Tapi mungkin

f \in A C 0

$f \in AC0$

L_{A} \in P H^{A}

$L_A \in PH^A$

A

$A$

t

$t$

A_{n}

$A_n$

n

$n$

t

$t$

1^{n} \in L_{A} ?

$1^n \in L_A?$

f

$f$

L_{A} \notin P P^{A}

$L_A \not\in PP^A$

...

L_{A} \in P P^{A} | p o l y

$L_A \in PP^A|poly$

Noam

Jadi untuk mendapatkan juga

kita perlu mengemas banyak instance

menjadi panjang tunggal

. Ini sepertinya mudah dilakukan dengan mendefinisikan

, di mana untuk string

bit

menunjukkan

bit yang menggambarkan apakah

untuk semua

L_{A} \notin P P^{A} / p o l y

$L_A \not\in PP^A/poly$

f

$f$

n

$n$

L_{A} = {x | f (A_{x}) = 1}

$L_A = \{ x | f(A_x)=1\}$

n

$n$

x

$x$

A_{x}

$A_x$

2^{n}

$2^n$

x y \in A

$xy \in A$

mungkin

dengan panjang

. Tetapi kita perlu meningkatkan batas bawah untuk

untuk mensyaratkan bahwa

salinan

padastring

bit yangberbedatidak dapat dihitung oleh gerbang ambang batas polylog (N), bahkan dengan bit bantuan polylog (N). Jadi ini harus salah untuk

. Tampaknya batas atas yang menarik.

2^{n}

$2^n$

y

$y$

n

$n$

f

$f$

N

$N$

f

$f$

N

$N$

f \in A C 0

$f \in AC0$

Noam

Kalau dipikir-pikir, pengamatan bahwa di bawah setiap ramalan yang membuat PH / ⊆ PP tidak ada PRG efisien yang menipu algoritma BP.PP seharusnya tidak lebih mengejutkan daripada fakta bahwa di bawah setiap ramalan yang membuat BPP / ⊆ P ada tidak ada PRG efisien yang menipu algoritma BPP. Itu karena setiap ramalan yang membuat PH / ⊆ PP juga membuat BP.PP / ⊆ PP oleh teorema Toda (relativized). Tapi mungkin saya tidak mengerti intinya. -

slimton

P^{A} \neq B P P^{A}

$P^A \ne BPP^A$

B P P^{A}

$BPP^A$

P^{A} / p o l y

$P^A/poly$

P H^{A} ⊈ P P^{A}

$PH^A \not\subseteq PP^A$

P^{A}

$P^A$

P P^{A}

$PP^A$

Noam

Seperti yang saya katakan di atas: dalam konstruksi untuk inti dari konstruksi adalah memberikan kekuatan "tidak alami" kepada BPP (dan dengan demikian juga untuk P / poli) dengan misalnya menanam banyak saksi untuk ramalan keras di tempat-tempat di mana hanya pengacakan yang dapat menemukannya. Jadi sementara memang menarik bahwa kekuatan ini cukup untuk masalah "umum" setidaknya kekuatan yang tak terduga P / poli jelas. Di sisi lain, saya tidak bisa melihat di mana pun bahwa oracle untuk memisahkan PH dari PP memberikan kekuatan tidak alami untuk P / poly atau kelas lain, pada kenyataannya. Saya tidak yakin bahwa perbedaan ini "nyata".

P \neq B P P

$P \ne BPP$

Noam

Lebih lanjut tentang PH dalam PP?

Jawaban: