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

8

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 { x : y zΣ2 , em que C é um circuito de tamanho polinomial que pode variar dependendo do comprimento da sequência de entrada x , e y , z também possuem comprimentos polinomiais em x .{x:yzC(x,y,z)}xy,zx

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?

Danny Nguyen
fonte

Respostas:

6

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:PH

  • Para uma direcção, modificar a prova de Karp-Lipton para mostrar que se então P H entra em colapso, e observa-se que este resultado relativizaNPcoNP/poeuyPH
  • Para a outra direção, veja os comentários de Kaveh abaixo.
Joshua Grochow
fonte
1
Can colapso mas n u P H não colapso? PHnvocêPH
Daniel Apon 9/17
1
@ 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
2
@Kaveh: Como? Posso estar sendo lento, mas eu não vê-lo ainda ...
Joshua Grochow
4
Suponha que P = NP. Considere L em PH / poli. Suponhamos que L Σ P k / poli, ou seja, χ L ( x ) = χ L ( x , f ( | x | ) ) para alguma função de aconselhamento f poli e L 'esteja em Σ P k . Mas L 'está em P, portanto L está em P / poli. ΣkPχeu(x)=χeu(x,f(|x|))ΣkP
22417 Kaveh
3
Provavelmente melhor ficar com : DPH/poly
Daniel Apon