Versão não uniforme para toda a hierarquia polinomial

As versões não uniformes de P, NP e coNP são P / poli, NP / poli e coNP / poli. Da mesma forma, podemos definir uma versão não uniforme para cada nível no PH.

Por exemplo: / poly consiste em problemas no formato $\Sigma_2$ , em que C é um circuito de tamanho polinomial que pode variar dependendo do comprimento da sequência de entrada , e também possuem comprimentos polinomiais em . $\{x : \exists y \forall z \; C(x,y,z)\}$ $x$ $y,z$ $x$

Fazendo isso para todos os níveis de PH, obtemos uma versão não uniforme PH / poly.

PERGUNTAS: Existe algo conhecido sobre essa hierarquia? Colapsa? Ou existe outro nome para isso na literatura?

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

Respostas:

Bem, claro, sabemos coisas. Eu acho que essa é uma nomenclatura bastante padrão para isso. Essa hierarquia entra em colapso se e somente se , exercitar: $\mathsf{PH}$

Para uma direcção, modificar a prova de Karp-Lipton para mostrar que se então entra em colapso, e observa-se que este resultado relativiza $\mathsf{NP} \subseteq \mathsf{coNP}/poly$ $\mathsf{PH}$
Para a outra direção, veja os comentários de Kaveh abaixo.

Joshua Grochow
fonte

Can

colapso mas

não colapso?

P H

$\mathsf{PH}$

n u P H

$\mathsf{nuPH}$

Daniel Apon 9/17

@ Daniel, acho que você pode se livrar da uniformidade dos quantificadores no circuito, então sim, se a PH os colapsar, o nuPH também.

Kaveh

@Kaveh: Como? Posso estar sendo lento, mas eu não vê-lo ainda ...

Joshua Grochow

Suponha que P = NP. Considere L em PH / poli. Suponhamos que L

/ poli, ou seja,

para alguma função de aconselhamento f

poli e L 'esteja em

. Mas L 'está em P, portanto L está em 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$

22417 Kaveh

Provavelmente melhor ficar com

: D

P H / p o l y

$\mathsf{PH/poly}$

Daniel Apon