Versi tidak seragam untuk seluruh hierarki polinomial

Versi P, NP dan coNP yang tidak seragam adalah P / poly, NP / poly dan coNP / poly. Demikian pula, kita dapat mendefinisikan versi yang tidak seragam untuk setiap level di PH.

Sebagai contoh: / poly terdiri dari masalah bentuk , di mana C adalah sirkuit dari ukuran polinomial yang dapat bervariasi tergantung pada panjang string input , dan juga memiliki panjang polinomial dalam . $\Sigma_2$ $\{x : \exists y \forall z \; C(x,y,z)\}$ $x$ $y,z$ $x$

Melakukan ini untuk semua level PH, kami mendapatkan versi PH / poli yang tidak seragam.

PERTANYAAN: Apakah ada yang diketahui tentang hierarki ini? Apakah itu runtuh? Atau adakah nama lain untuk itu dalam literatur?

cc.complexity-theory complexity-classes polynomial-hierarchy Danny Nguyen
sumber

Jawaban:

Tentu, kami tahu banyak hal. Saya pikir ini adalah nomenklatur yang cukup standar untuk itu. Hirarki ini runtuh jika dan hanya jika melakukannya, berolahraga: $\mathsf{PH}$

Untuk satu arah, modifikasi bukti Karp-Lipton untuk menunjukkan bahwa jika lalu runtuh, dan amati bahwa hasil ini relativizes $\mathsf{NP} \subseteq \mathsf{coNP}/poly$ $\mathsf{PH}$
Untuk arah lain, lihat komentar oleh Kaveh di bawah ini.

Joshua Grochow
sumber

Can

runtuhnya tapi

tidak runtuh?

P H

$\mathsf{PH}$

n u P H

$\mathsf{nuPH}$

Daniel Apon

@ Danielel, saya pikir Anda bisa menghilangkan keseragaman bilangan di sirkuit, jadi ya, jika PH runtuh begitu juga nuPH.

Kaveh

@ Kaveh: Bagaimana? Saya mungkin lambat, tetapi saya belum melihatnya ...

Joshua Grochow

Asumsikan P = NP. Pertimbangkan L dalam PH / poli. Mari kita asumsikan L

/ poli, yaitu

untuk beberapa fungsi saran f

poli dan L 'ada di

. Tapi L 'ada di P, oleh karena itu L ada di P / poli.

\in

$\in$

Σ_{k}^{P}

$\Sigma^P_k$

χ_{L} (x) = χ_{L^{'}} (x, f (| x |))

$\chi_L(x) = \chi_{L'}(x,f(|x|))$

\in

$\in$

Σ_{k}^{P}

$\Sigma^P_k$

Kaveh

Mungkin lebih baik tetap dengan

: D

P H / p o l y

$\mathsf{PH/poly}$

Daniel Apon