Faz

37

Tanto quanto eu entendo, o programa da teoria da complexidade geométrica tenta separar , provando que o permamento de uma matriz de valor complexo é muito mais difícil de calcular do que o determinante.VPVNP

A pergunta que tive depois de examinar os Documentos do GCT: Isso implicaria imediatamente , ou é apenas um passo importante para esse objetivo?PNP

Benno
fonte
3
AFAIK, o zoológico fornece todas as informações conhecidas. qwiki.stanford.edu/wiki/Complexity_Zoo:V#vnp
Michaël Cadilhac
A monografia "Completude e redução da teoria da complexidade algébrica", de Peter Bürgisser (math-www.uni-paderborn.de/agpb/work/habil.ps), pode fornecer uma idéia melhor sobre a questão.
MCH
Atualizando o URL de Michaël: complexzoo.uwaterloo.ca/Complexity_Zoo:V#vnp
András Salamon

Respostas:

27

A resposta curta é não'. Nenhuma implicação desse tipo é conhecida. Existem dois obstáculos principais: passar da complexidade do circuito aritmético para a complexidade booleana (VP ≠ VNP implica P / poly ≠ NP / poly) e depois passar da complexidade do circuito booleano (P / poly ≠ NP / poly) para a complexidade uniforme (P ≠ NP ) Nenhuma dessas etapas é conhecida. Eu acredito que P / poli ≠ NP / poli implica VP ≠ VNP, no entanto.

Moritz
fonte
4
Sua última frase é verdadeira: se houver um campo em que VP = VNP, P / poly = NP / poly (siga o link no comentário de Cadilhac).
Diego de Estrada
22

Assumindo a hipótese generalizada de Riemann (GRH), são conhecidas as seguintes conexões bastante fortes entre e o colapso da hierarquia polinomial ( P H ):VP=VNPPH

  1. Se VP=VNP (sobre qualquer campo), a hierarquia polinomial cai para o segundo nível;
  2. Se VP=VNPao longo de um campo de característica , em seguida, N C 3 / p o l y = P / p o l y = P H / p o l y ;0NC3/poly=P/poly=PH/poly
  3. Se VP=VNPao longo de um campo finito de característica , em seguida, N C 2 / p o l y = P / p o l y = P H / p o l y .pNC2/poly=P/poly=PH/poly

Estes são os resultados de: Peter Burgisser, " hipótese de Cook versus Valiant ", Theor. Comp. Sci., 235: 71-88, 2000.

Veja também: Burgisser, " Completude e redução na teoria da complexidade algébrica ", 1998.

Iddo Tzameret
fonte
11
Eu acho que você quis dizer que implica o colapso da hierarquia polinomial, não que V P V N P implica isso. VP=VNPVPVNP
Robin Kothari
15

Posso dar-lhe uma razão informal por que a separação não provaria .PNP

VP e VNP enfocam funções algébricas cujo grau é delimitado por um polinômio. Observe que é fácil calcular em uma função algébrica de grau exponencial com um circuito algébrico de tamanho polinomial.

Existe uma redução bem conhecida de 1 profundidade para circuitos algébricos: qualquer circuito algébrico de tamanho polinomial que computa um polinômio de grau pode ser transformado em um circuito algébrico de tamanho polinomial e profundidade O ( log d log n ) .dO(logdlogn)

Pode pensar em como uma variante algébrica de N C 2 , provando assim que V P V N P eleva-se a provar a um equivalente não uniforme algébrica de N C 2# P . Isso não descartaria P = N P , pelo menos não imediatamente.VPNC2VPVNPNC2#PP=NP

Isenção de responsabilidade : não consigo acessar o artigo no momento e não me lembro se a redução funciona em qualquer campo ou apenas em áreas finitas.

1 LG Valiant, S. Skyum, S. Berkowitz, C. Rackoff. Rápida computação paralela de polinômios usando poucos processadores . SIAM J. Comput. 12 (4), pp. 641-644, 1983.

MassimoLauria
fonte
2
é o equivalente não uniforme algébrico de ou N C 2# P ? NC2NPNC2#P
Joshua Grochow
VNPNP#P
2
Valiant et al. resultado funciona para qualquer campo.
Iddo Tzameret