Apakah ?

37

Kita tahu bahwa level pertama dari hierarki polinomial (yaitu NP dan co-NP) adalah dalam PP, dan bahwa . Kita juga tahu dari Teorema Toda bahwa . $PP \subseteq PSPACE$ $PH \subseteq P^{PP}$

Apakah kita tahu apakah ? Jika tidak, mengapa dengan lebih kuat dari ? Apakah mungkin dan ? $PH \subseteq PP$ $P$ $PP$ $PP$ $PH \nsubseteq PP$ $PP \nsubseteq PH$

Pertanyaan ini sangat sederhana, tetapi saya belum menemukan sumber daya yang menanganinya.

Saya bertanya ini pertanyaan yang terkait tapi jauh kurang spesifik pada matematika melimpah sebelum belajar lebih lanjut tentang topik.

Berikut ini adalah pertanyaan yang agak terkait (tetapi berbeda): Apakah $coNP^{\#P}=NP^{\#P}=P^{\#P}$ ?

Pembaruan: Lihatlah pertanyaan Noam Nisan di sini: Selengkapnya tentang PH dalam PP?

cc.complexity-theory counting-complexity polynomial-hierarchy Huck Bennett
sumber

37

Huck, seperti yang ditunjukkan Lance dan Robin, kami memiliki nubuat relatif yang PH tidak ada dalam PP. Tetapi itu tidak menjawab pertanyaan Anda, seperti itulah situasinya di dunia "nyata" (tidak berhubungan)!

Jawaban singkatnya adalah bahwa (seperti banyak hal lain dalam teori kompleksitas) kita tidak tahu.

Tetapi jawaban yang lebih panjang adalah bahwa ada alasan yang sangat bagus untuk menduga bahwa memang PH ⊆ PP.

Pertama, Teorema Toda menyiratkan PH ⊆ BP.PP, di mana BP.PP adalah kelas kompleksitas yang "adalah untuk PP seperti BPP adalah untuk P" (dengan kata lain, PP di mana Anda dapat menggunakan pengacakan untuk menentukan perhitungan UTAMA yang ingin Anda hitung) melakukan). Kedua, di bawah hipotesis derandomisasi yang masuk akal (mirip dengan yang diketahui menyiratkan P = BPP, oleh Nisan-Wigderson, Impagliazzo-Wigderson, dll.), Kita akan memiliki PP = BP.PP.

Tambahan, untuk menjawab pertanyaan Anda yang lain:

(1) Saya akan mengatakan bahwa kita tidak memiliki intuisi yang menarik baik pada pertanyaan apakah PP = P ^PP . Kita tahu, dari hasil Beigel-Reingold-Spielman dan Fortnow-Reingold, bahwa PP ditutup di bawah pengurangan non - adaptif (tabel kebenaran). Dengan kata lain, mesin P yang dapat membuat permintaan paralel ke oracle PP tidak lebih kuat dari PP itu sendiri. Tetapi fakta bahwa hasil ini sepenuhnya rusak untuk permintaan adaptif (non-paralel) ke oracle PP menunjukkan bahwa mungkin yang terakhir ini benar-benar lebih kuat.

(2) Demikian juga, NP ^PP dan CONP ^PP mungkin masih lebih kuat daripada P ^PP . Dan PP ^PP mungkin masih lebih kuat, dan seterusnya. Urutan P, PP, P ^PP , PP ^PP , P ^{PP ^ PP} , dll disebut hierarki penghitungan , dan seperti halnya orang mengira bahwa PH tidak terbatas, demikian juga seseorang dapat menduga (meskipun mungkin dengan kurang percaya diri!) Bahwa CH tidak terbatas. Ini terkait erat dengan keyakinan bahwa, dalam sirkuit ambang kedalaman konstan (yaitu, jaringan saraf), menambahkan lebih banyak lapisan gerbang ambang memberikan Anda kekuatan komputasi yang lebih besar.

Scott Aaronson
sumber

7

Scott, saya agak bingung dengan pernyataan bahwa "masuk akal" PP akan berisi PH. Pemisahan pertama PH dari PP melalui nubuat memiliki inti kombinatorial pemisahan Minski & Papert yang asli bahwa AND-of-OR tidak dapat disimulasikan oleh gerbang ambang batas derajat-polylog. Saya berpikir bahwa versi non-seragam Toda mensimulasikan AC0 oleh distribusi probabilitas lebih dari gerbang ambang derajat-polylog yang mendapatkan jawaban yang benar whp. Jadi pada level non-seragam, "BP" -ganda menambahkan kekuatan yang signifikan, tidak seperti untuk P vs BPP atau NP vs AM yang tidak seragam. Jadi misalnya apakah PH dalam PP dengan oracle acak?

Noam

Noam, bukankah PP dengan oracle acak mengandung BP.PP? (Saya tidak mengerti mengapa tidak seharusnya.) Jika demikian, maka pasti PH dalam PP dengan oracle acak. Tetapi izinkan saya mengajukan pertanyaan lain: adakah kompleksitas kelas C yang kita punya alasan kuat untuk percaya bahwa C tidak sama dengan BP.C?

Scott Aaronson

Anda perlu amplifikasi untuk menunjukkan bahwa PP = BP.PP dengan oracle acak - Saya tidak melihat bagaimana melakukannya. Bahkan secara tidak seragam, saya tidak dapat melihat bahwa PH ada dalam PP / poli. Bukankah AND-of-ORs yang tidak ada dalam ambang batas polylog tampaknya menunjukkan bahwa bahkan PH yang tidak seragam tidak ada dalam PP?

Noam

Berikut makalah yang menunjukkan BP.PP = PP di bawah hipotesis yang masuk akal: www.cs.uwyo.edu/~jhitchco/papers/hhdcc.ps

Scott Aaronson

8

Apa yang saya lewatkan adalah bahwa Fortnow dan Reingold menunjukkan bahwa PP ditutup di bawah pengurangan kebenaran, sebuah penutupan yang diperlukan untuk derandomisasi menggunakan PRG (atau tidak seragam atau dengan oracle acak). Namun saya masih bingung di sini, dan merumuskan pertanyaan tentang hal itu: cstheory.stackexchange.com/questions/3331/more-on-ph-in-pp

Noam

23

Richard Beigel memiliki oracle relatif dimana tidak terkandung dalam PP. $P^{NP}$

Lance Fortnow
sumber

20

Vereshchagin [Ver] menunjukkan bahwa ada oracle relatif yang AM tidak terkandung dalam PP. (Hasil ini tampaknya tidak sebanding dengan hasil vs PP.) $P^{NP}$

[Ver] NK Vereshchagin. Tentang kekuatan PP , Prosiding IEEE Complexity'92, hlm. 138-143, 1992.

Robin Kothari
sumber

13

Sesuatu yang belum disebutkan sejauh ini (sejauh yang saya bisa lihat) dan yang berlaku di dunia yang tidak ter-relativis adalah sebagai berikut:

P H \subseteq P P if Q M A = P P .

$PH \subseteq PP \quad\mbox{ if }\quad QMA = PP.$

Ini diamati oleh Vyalyi dalam makalah ini dan berasal dari penguatan dua teorema:

Teorema Toda - Vyalyi menunjukkan bahwa satu permintaan ke oracle cukup untuk " mesin " untuk mensimulasikan . $\sharp P$ $P$ $PH$
Dimasukkannya dibuktikan oleh Kitaev dan Watrous. Vyalyi membuktikan bahwa juga ada di , kelas yang terkandung dalam . $QMA \subseteq PP$ $QMA$ $A_0PP$ $PP$

Alessandro Cosentino
sumber

Apakah ?

Jawaban: