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?
(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
fonte
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.
fonte
Este artigo é relevante, pois tenta mostrar que PPAD = P: https://arxiv.org/abs/1609.08934
fonte