Masalah yang ada di PSPACE tetapi tidak diketahui berada di PH?

8

Seperti yang kita ketahui, Graph Isomorphism ada dalam NP tetapi tidak diketahui sebagai NP-Complete atau P-Complete. Saya bertanya-tanya apakah ada masalah yang diketahui berada di PSPACE tetapi tidak dikenal sebagai PSPACE-Lengkap dan tidak terletak pada PH?

Tayfun Pay
sumber
4
Apakah ada masalah PSPACE-complete? Mungkin Anda mengajukan pertanyaan yang salah.
5501
1
Apakah Anda bertanya apakah PH = PSPACE?
Mohammad Al-Turkistany
11
Jika Anda bermaksud untuk meminta masalah yang dianalogikan dengan GI, maka mungkin Anda meminta masalah yang tidak ada di PH dan tidak lengkap dengan PSPACE. Masalah yang diselesaikan untuk setiap kelas yang tidak diketahui terkandung dalam PH, tetapi terkandung dalam PSPACE, akan berfungsi sebagai contoh. Jadi, selesaikan masalah apa pun untuk BQP, QMA, PP, dll.
Robin Kothari
7
Juga, teori eksistensial real dikenal di PSPACE tetapi bukan PH.
Peter Shor
4
@Robin, @ Peter, kedua hal ini adalah jawaban, tidak komentar :)
Suresh Venkat

Jawaban:

23

The teori eksistensial dari real diketahui terkandung dalam PSPACE, tetapi tidak diketahui apakah itu terkandung dalam PH. Jadi, ambil teori eksistensial dari real, atau salah satu dari banyak masalah yang setara.

Peter Shor
sumber
Apa yang Anda maksud dengan masalah lengkap? Teori eksistensial real adalah masalah tunggal, bukan kelas.
Emil Jeřábek
1
@ Emil: diperbaiki sekarang. Ada cukup banyak masalah yang setara yang saya anggap sebagai kelas kompleksitas, tapi saya minoritas di sini.
Peter Shor
Begitu ya, ini masuk akal.
Emil Jeřábek
19

PP

Dai Le
sumber
18

Menyalin komentar saya:

Jika Anda bermaksud untuk meminta masalah yang dianalogikan dengan GI, maka mungkin Anda meminta masalah yang tidak ada di PH dan tidak lengkap dengan PSPACE. Masalah yang diselesaikan untuk setiap kelas yang tidak diketahui terkandung dalam PH, tetapi terkandung dalam PSPACE, akan berfungsi sebagai contoh. Jadi selesaikan masalah apa pun untuk BQP, QMA, PP, dll.

Robin Kothari
sumber
1

Setiap masalah yang MP-Complete, Kelas masalah keputusan sehingga untuk beberapa fungsi #P f, jawaban pada input x adalah 'ya' jika dan hanya jika bit tengah f (x) adalah 1. [Definisi adalah dari Kebun Binatang Kompleksitas].
Telah ditunjukkan bahwa PH ⊆ MP ⊆ PSPACE.

Tayfun Pay
sumber
1

Masalah ParitySat adalah untuk memeriksa apakah masalah SAT memiliki jumlah penugasan memuaskan yang ganjil. PH dapat direduksi menjadi ParitySAT melalui reduksi acak oleh karya Toda. Ini adalah masalah keputusan yang jelas-jelas ketat antara PH dan PSACE kecuali PH runtuh.

Bin Fu
sumber
Ya ada dua akibat wajar dari teorema Toda yang menyatakan bahwa ParityP atau PP berada di dalam PH kecuali jika PH runtuh ke tingkat yang terbatas.
Tayfun Bayar