En informática , PPAD ("Argumentos de paridad polinómica en gráficos dirigidos") es una clase de complejidad introducida por Christos Papadimitriou en 1994. PPAD es una subclase de TFNP basada en funciones que se puede demostrar que son totales mediante un argumento de paridad. [1] [2] La clase atrajo una atención significativa en el campo de la teoría algorítmica de juegos porque contiene el problema de calcular un equilibrio de Nash : Daskalakis, Goldberg y Papadimitriou demostraron que este problema era completo para PPAD con al menos 3 jugadores y Posteriormente, Chen y Deng lo ampliaron a 2 jugadores. [3] [4]
PPAD es un subconjunto de la clase TFNP , la clase de problemas de función en FNP que se garantiza que son totales . La definición formal de TFNP se da de la siguiente manera:
Las subclases de TFNP se definen en función del tipo de prueba matemática utilizada para demostrar que siempre existe una solución. De manera informal, PPAD es la subclase de TFNP donde la garantía de que existe una y tal que se cumple P( x , y ) se basa en un argumento de paridad en un gráfico dirigido. La clase se define formalmente especificando uno de sus problemas completos, conocido como End-Of-The-Line :
Tal t debe existir si existe una s , porque la estructura de G significa que los vértices con un solo vecino vienen en pares. En particular, dada s , podemos encontrar tal t en el otro extremo de la cadena que comienza en s . (Tenga en cuenta que esto puede tomar un tiempo exponencial si solo evaluamos f repetidamente).
PPAD está contenido en (pero no se sabe que sea igual a) PPA (la clase correspondiente de argumentos de paridad para gráficos no dirigidos) que está contenido en TFNP. PPAD también está contenido en (pero no se sabe que sea igual a) PPP , otra subclase de TFNP. Contiene CLS . [5]
PPAD es una clase de problemas que se cree que son difíciles, pero obtener la completitud de PPAD es una evidencia más débil de intratabilidad que la obtención de la completitud de NP . Los problemas PPAD no pueden ser NP-completos, por la razón técnica de que NP es una clase de problemas de decisión, pero la respuesta de los problemas PPAD siempre es sí, ya que se sabe que existe una solución, aunque puede ser difícil encontrar esa solución. [6] Sin embargo, PPAD y NP están estrechamente relacionados. Mientras que la pregunta de si existe un equilibrio de Nash para un juego dado no puede ser NP-difícil porque la respuesta siempre es sí, la pregunta de si existe un segundo equilibrio es NP completa. [7] Todavía podría darse el caso de que PPAD sea de la misma clase que FP, y todavía tenemos que P ≠ NP , aunque parece poco probable. [ cita requerida ] Ejemplos de problemas completos de PPAD incluyen encontrar equilibrios de Nash , calcular puntos fijos en funciones de Brouwer y encontrar equilibrios de Arrow-Debreu en los mercados. [8]