Apa konsekuensi dari PH = PSPACE?

Sebuah pertanyaan baru-baru ini (lihat Konsekuensi dari NP = PSPACE ) meminta "jahat" konsekuensi dari $NP=PSPACE$ . Jawaban daftar beberapa konsekuensi keruntuhan, termasuk $NP=coNP$ dan lain-lain, memberikan banyak alasan untuk percaya $NP\neq PSPACE$ .

Apa yang akan menjadi konsekuensi dari kehancuran yang agak kurang dramatis ? $PH=PSPACE$

cc.complexity-theory complexity-classes conditional-results Andras Farago
sumber

Apakah saya satu-satunya orang yang bosan dengan lonjakan pertanyaan "Konsekuensi

" hari ini? Memang, mereka dapat menghasilkan jawaban yang menarik, tetapi pertanyaannya setidaknya harus menanyakan konsekuensi yang tidak terduga , mengejutkan , dll.

A = B

$A=B$

Sylvain

@ Silvain: beberapa dari mereka sebenarnya pertanyaan lama yang telah bangkit dari kematian karena saya menambahkan tag "hasil kondisional" kepada mereka. Anda kemudian dapat memilih untuk mengabaikan tag itu untuk membuat pertanyaan seperti itu kurang terlihat bagi Anda.

András Salamon

Jawaban:

runtuh. Sebuah masalah -Lengkap harus dalam beberapa tingkat , mengatakan itu di . Sejak itu -Lengkap -Lengkap (oleh asumsi), . $\mathsf{PH}$ $\mathsf{PSPACE}$ $\mathsf{PH}$ $\mathsf{\Sigma_k P}$ $\mathsf{PSPACE}$ $=\mathsf{PH}$ $\mathsf{PH} \subseteq \mathsf{\Sigma_k P}$

Joshua Grochow
sumber

Bukankah

ditutup dengan komplemen dan rendah untuk dirinya sendiri? Itu adalah

Jadi bukankah itu menyiratkan

dan

P S P A C E

${\bf PSPACE}$

P S P A C E

${\bf PSPACE}$

{P S P A C E}^{P S P A C E}

${\bf PSPACE}^{\bf PSPACE}$

N P = C o N P

${\bf NP} = {\bf CoNP}$

N P = P S P A C E

${\bf NP} ={\bf PSPACE}$

Tayfun Bayar

@TayfunPay:

$\:$ Saya tidak melihat bagaimana implikasi seperti itu dapat ditunjukkan.

$\;\;\;\;$

@TayfunPay: Perhatikan bahwa

- ketika dianggap sebagai kelas tunggal yang didefinisikan dengan bergantian poly-time TM's dengan

alternatif - juga ditutup di bawah komplemen dan self-low (bahkan tanpa menganggap itu sama dengan

P H

$\mathsf{PH}$

O (1)

$O(1)$

P S P A C E

$\mathsf{PSPACE}$

Joshua Grochow

@ JoshuaGrochow Bukankah keberadaan PH-Lengkap menyiratkan bahwa

runtuh? Saya ingat sesuatu seperti ini ada di buku Papadimitriou lama. Saya akan memeriksanya malam ini.

P H

${\bf PH}$

Tayfun Bayar

@TayfunPay: Ya, menggunakan bukti yang sama dengan jawaban saya (tapi itu tidak, dan sepertinya tidak bisa, katakan level apa yang runtuh karena asumsi itu).

Joshua Grochow

Itu masih akan menyiratkan pemisahan utama dari kelas kompleksitas. Sebagai contoh, akan mengikuti. (Jika maka ) $\mathrm{LOGSPACE \neq NP}$ $\mathrm{LOGSPACE = NP}$ $\mathrm{LOGSPACE = PH}$

Juga akan menyiratkan oleh Karp-Lipton. Oleh karena itu memiliki sirkuit polysize jika dan hanya jika tidak. Dan tentu saja, kita harus IFF . Bagaimanapun, konsekuensi dari penyelesaian $\mathrm{NP \subseteq P/poly}$ $\mathrm{PSPACE = \Sigma_2 P}$ $\mathrm{NP}$ $\mathrm{PSPACE}$ $\mathrm{P = NP}$ $\mathrm{P = PSPACE}$ $\mathrm{NP}$ masalah secara efisien akan meningkat secara signifikan.

Ryan Williams
sumber

N P^{N L \cap c o - N L} = N P

$NP^{NL\cap co-NL}=NP$ .

domotorp

As the answers point out, $PH=PSPACE$ would still have significant consequences, even though not as numerous and dramatic ones as $NP=PSPACE$ .

Turning the issue on its head, it could be viewed as "empirical evidence" to support $NP\neq PH$ . After all, if $NP=PH$ , then the two statements ( $PH=PSPACE$ and $NP=PSPACE$ ) must have the same consequences. As the second hypothesis has noticeably more and stronger known consequences, that can be viewed as empirical evidence to support that the left-hand sides in the equations must be different, that is $NP\neq PH$ (which, in turn, is equivalent to $NP\neq coNP$ ).

Andras Farago
sumber