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 . { x : ∃ y ∀ zx 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?
sumber