Evidência de que o PPAD é difícil?

32

Há uma justificativa filosófica frequentemente citada para acreditar que P! = NP mesmo sem prova. Outras classes de complexidade têm evidências de que são distintas, porque, se não, haveria consequências "surpreendentes" (como o colapso da hierarquia polinomial).

Minha pergunta é: qual é a base para a crença de que a classe PPAD é intratável? Se houvesse um algoritmo polinomial de tempo para encontrar equilíbrios de Nash, isso implicaria algo sobre outras classes de complexidade? Existe um argumento heurístico para o porquê de ser difícil?

Aaron Roth
fonte

Respostas:

28

O PPAD é bastante "baixo" acima de P e pouco mudaria em nossa compreensão da complexidade se fosse mostrado igual a P (exceto que os poucos problemas no PPAD estariam agora em P). A principal "evidência" de que o PPAD! = P é uma separação do oráculo, que é essencialmente equivalente ao fato combinatório de que não existe "simulação de caixa preta".

Noam
fonte
8

Buhrman et al. mostrou que existe um oráculo em relação ao qual todas as funções TFNP são computáveis ​​em tempo poligonal, mas a Hierarquia Polinomial é infinita. TFNP é uma classe que contém PPAD e seus primos. Esse é outro resultado que reforça nossa percepção de que o PPAD ser fácil não geraria conseqüências improváveis ​​na complexidade.

O artigo é "A hierarquia polinomial entra em colapso se as funções são invertíveis?"

disponível no site de Lance Fortnow. Parece que uma versão anterior do artigo foi intitulada "Inversão de funções e hierarquia polinomial" (a nova versão está sob esse antigo nome no site de Lance).

Andy Drucker
fonte
10
A rastreabilidade do TFNP seria significativamente mais surpreendente do que a do PPAD, uma vez que o primeiro descartaria a existência de permutações unidirecionais e implicaria P = (NP interseção coNP).
Noam
8

(Acho que ninguém nunca respondeu a essa pergunta mais antiga com os resultados mais recentes; aqui está você :)


E aqui está mais uma opção ainda mais recente para a dureza , por meio da criptografia funcional de chave privada : do Minicrypt ao Obfustopia via criptografia funcional de chave privadaPPAD

Daniel Apon
fonte
2

Embora isso tenha sido afetado de qualquer maneira, talvez eu possa ter a arrogância de mencionar uma heurística que vem à mente.

Um problema NP-completo é, dado um circuito, existe uma entrada avaliada como True?

  • Esse problema seria claramente fácil se a entrada fosse representada "explicitamente" como uma lista de pares de entrada e saída, em vez de "sucintamente" como um circuito.

  • O problema é claramente difícil em termos de informação se a entrada for uma função oracle de caixa preta em vez de um circuito (requer a tentativa de todas as entradas).

  • O problema em separar P de NP, se verdadeiro, está em mostrar que os programas não podem dissecar circuitos com eficiência.

Os problemas completos do PPAD compartilham algumas características interessantes aqui. Se você pensa em Fim de linha, ele "recebe um gráfico representado de forma sucinta, com algumas restrições, e uma fonte, encontre um coletor". E ele compartilha os três pontos acima, eu acho.

usul
fonte
-1

Este artigo é relevante, pois tenta mostrar que PPAD = P: https://arxiv.org/abs/1609.08934

Samuel Schlesinger
fonte
7
Existem inúmeros trabalhos mostrando P = NP. Eu não consideraria relevante até que seja devidamente revisado e publicado por pares.
Emil Jeřábek apoia Monica
O primeiro erro é a última linha da prova do Lema 10 na página 18, já que "f (alfa, eps) <0 para eps = 0 e lim_alpha f (alfa, eps) = infinito para eps> 0" não é impossível, mesmo que f (alpha, epsilon) seja uma função contínua de alpha e epsilon. Porém, como o artigo fornece um algoritmo explícito, você certamente também deseja um contra-exemplo explícito em que esse algoritmo falha, antes de poder alegar que refutou esse artigo.
Thomas Klimpel