¿Evidencia de que PPAD es difícil?

A menudo se cita una justificación filosófica para creer que P! = NP incluso sin pruebas. Otras clases de complejidad tienen evidencia de que son distintas, porque si no, habría consecuencias "sorprendentes" (como el colapso de la jerarquía polinómica).

Mi pregunta es, ¿cuál es la base para creer que la clase PPAD es intratable? Si hubiera un algoritmo de tiempo polinómico para encontrar equilibrios de Nash, ¿esto implicaría algo sobre otras clases de complejidad? ¿Existe un argumento heurístico de por qué debería ser difícil?

PPAD es bastante "bajo" por encima de P y no cambiaría mucho en nuestra comprensión de la complejidad si se mostrara igual a P (excepto que los pocos problemas en PPAD ahora estarían en P). La "evidencia" principal de que PPAD! = P es una separación de oráculo, que es esencialmente equivalente al hecho combinatorio de que no existe una "simulación de caja negra".

Buhrman y col. mostró que hay un oráculo con respecto al cual todas las funciones TFNP son computables en tiempo polivinílico, sin embargo, la Jerarquía polinómica es infinita. TFNP es una clase que contiene PPAD y sus primos. Este es otro resultado que fortalece nuestra sensación de que PPAD es fácil no generaría consecuencias poco probables en complejidad.

El artículo es "¿La jerarquía polinómica se colapsa si las funciones son invertibles?"

disponible en el sitio web de Lance Fortnow. Parece que una versión anterior del documento se tituló "Invertir en funciones y la jerarquía polinómica" (la nueva versión está bajo este antiguo nombre en el sitio de Lance).

(Creo que nadie respondió esta pregunta anterior con los resultados más nuevos; aquí tienes :)

• $\mathsf{PPAD}$
• $\mathsf{PPAD}$

$\mathsf{PPAD}$

Si bien esto se ha visto afectado de todos modos, tal vez pueda tener la arrogancia de mencionar una heurística que se me ocurra.

Un problema de NP completo es, dado un circuito, ¿hay una entrada que se evalúe como Verdadero?

• Este problema claramente sería fácil si la entrada se representara "explícitamente" como una lista de pares de entrada-salida, en lugar de "sucintamente" como un circuito.

• El problema es claramente difícil en términos de información si la entrada es una función oracle de caja negra en lugar de un circuito (requiere probar todas las entradas).

• El problema en la separación de P de NP, si es cierto, radica en mostrar que los programas no pueden diseccionar circuitos de manera eficiente.

Los problemas de PPAD completo comparten algunas características interesantes aquí. Si piensa en el final de la línea, se le "da una gráfica representada sucintamente con algunas restricciones, y una fuente, encuentra un sumidero". Y comparte los tres puntos anteriores, creo.

Este documento es relevante para esto, ya que intenta mostrar que PPAD = P: https://arxiv.org/abs/1609.08934