Apakah Parity-P terkandung dalam PP?

Pertanyaan ini ditanyakan oleh Jan Pax di milis Yayasan Matematika . Tentu saja tetapi saya menduga dari jawaban pertanyaan ini bahwa tidak diketahui apakah (jika tidak, akan menjadi satu kemungkinan jawaban untuk pertanyaan itu). Jika tidak diketahui, apakah ada pemisahan oracle? $P^{\oplus P} \subseteq P^{\#P} = P^{PP}$ $\oplus P \subseteq PP$ $PP$

cc.complexity-theory complexity-classes Timothy Chow
sumber

Wikipedia mengatakan bahwa ada oracle yang

P^{A} = \oplus P^{A} \neq N P^{A} (= P P^{A}) = E X P^{A}

$P^A = \oplus P^A \neq NP^A ( = PP^A) = EXP^A$ ( R. Beigel, H. Buhrman, dan L. Fortnow. NP mungkin tidak semudah itu sebagai mendeteksi solusi unik )

Marzio De Biasi

A

$A$

\oplus P^{A} ⊈ P P^{A}

$\oplus P^A \not\subseteq PP^A$

Apa yang akan saya katakan adalah jawaban dari jawaban yang lain, tetapi mungkin berguna jika Anda ingin menyederhanakannya. Peramalan yang Anda cari hanyalah aplikasi dari fakta lama yang diketahui bahwa perceptron tidak dapat menghitung PARITY (Minsky & Papert).

Alessandro Cosentino

@AlessandroCosentino Apakah dan ? Bagaimana jika benar?

P P^{\oplus P} = P P

$PP^{\oplus P}=PP$

{\oplus P}^{P P} = P P

${\oplus P}^{PP}=PP$

P P \subseteq \oplus P

$PP\subseteq\oplus P$

T ....

Jawaban:

Ya, ada oracle sehingga . Bahkan, ada oracle sehingga . Anda dapat menemukan hasilnya di kertas berikut. $A$ $\oplus P^A \not\subseteq PP^A$ $A$ $\oplus P^A \not\subseteq PP^{PH^A}$

Frederic Green, sebuah oracle yang memisahkan dari , Surat Pemrosesan Informasi, Volume 37, Edisi 3, 18 Februari 1991, Halaman 149-153 $\oplus P$ $PP^{PH}$

Robin Kothari
sumber

Terima kasih ... ini persis apa yang saya cari! Dalam komentar pembukaan untuk makalahnya, Green memuji Ph.D. Jacobo Torán tesis dengan oracle pertama

sehingga

. Hasil ini kemudian diterbitkan sebagai Teorema 5.13 dalam makalah Torán "Kelas kompleksitas didefinisikan dengan menghitung bilangan," JACM 38 (1991), 752-773.

A

$A$

\oplus P^{A} ⊈ P P^{A}

$\oplus P^A \not\subseteq PP^A$

Timothy Chow

Scott Aaronson memberikan oracle di mana P = PEXP yang menyiratkan oracle yang Anda inginkan. http://eccc.hpi-web.de/report/2005/040/download/ (Teorema 12 dalam lampiran) $\oplus$

Lance Fortnow
sumber

Terima kasih. Saya harus memilih hanya satu jawaban untuk diterima, jadi saya memilih jawaban Robin Kothari karena ini adalah referensi sebelumnya.

Timothy Chow