PPAD (complejidad)

En informática , PPAD ("Argumentos de paridad polinomial en grafos dirigidos") es una clase de complejidad introducida por Christos Papadimitriou en 1994. PPAD es una subclase de TFNP basada en funciones que pueden demostrarse totales mediante un argumento de paridad. ^{[ 1 ] [ 2 ]} La clase atrajo una atención significativa en el campo de la teoría de juegos algorítmica 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 extendieron a 2 jugadores. ^{[ 3 ] [ 4 ]}

PPAD es un subconjunto de la clase TFNP , la clase de problemas de función en FNP que están garantizados como totales . La definición formal de TFNP se da de la siguiente manera:

Una relación binaria P( x , y ) está en TFNP si y solo si hay un algoritmo determinista de tiempo polinomial que puede determinar si P( x , y ) se cumple dados x e y , y para cada x , existe un y tal que P( x , y ) se cumple.

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 un y tal que P( x , y ) se cumple se basa en un argumento de paridad en un grafo dirigido. La clase se define formalmente especificando uno de sus problemas completos, conocido como End-Of-The-Line :

G es un grafo dirigido (posiblemente de tamaño exponencial) donde cada vértice tiene como máximo un predecesor y como máximo un sucesor. G se especifica mediante una función computable en tiempo polinomial f( v ) (polinomial en el tamaño de v ) que devuelve el predecesor y el sucesor (si existen) del vértice v . Dado un vértice s en G sin predecesor, encontrar un vértice t≠s sin predecesor ni sucesor. (La entrada al problema es el vértice fuente s y la función f( v )). En otras palabras, queremos cualquier fuente o sumidero del grafo dirigido distinto de s .

Tal t debe existir si existe un s , porque la estructura de G implica que los vértices con un solo vecino aparecen en pares. En particular, dado s , podemos encontrar tal t en el otro extremo de la cadena que comienza en s . (Tenga en cuenta que esto puede llevar un tiempo exponencial si simplemente evaluamos f repetidamente).

En muchos casos, cuando se dice que un problema "está en PPAD", a menudo significa que encontrar una solución aproximada al problema está en PPAD. Esto suele ser necesario, ya que en muchos casos las soluciones pueden involucrar números irracionales y, por lo tanto, no se pueden obtener en un tiempo finito. ^{[ 5 ]}

Sin embargo, existen casos en los que se garantiza la existencia de soluciones con números racionales. Para tales casos, Filos-Ratsikas, Hansen, Høgh y Hollender ^{[ 5 ]} presentan un método general para demostrar que el cálculo de una solución exacta pertenece a PPAD.

PPAD está contenido en (pero no se sabe que sea igual a) PPA (la clase correspondiente de argumentos de paridad para grafos 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 . ^{[ 6 ]}

PPAD es una clase de problemas que se consideran difíciles, pero obtener PPAD-completitud es una evidencia más débil de intratabilidad que obtener NP-completitud . 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 a los problemas PPAD siempre es sí, ya que se sabe que existe una solución, aunque puede ser difícil encontrarla. ^{[ 7 ]} Sin embargo, PPAD y NP están estrechamente relacionados. Si bien 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. ^{[ 8 ]} Ejemplos de problemas PPAD-completos incluyen encontrar equilibrios de Nash , calcular puntos fijos en funciones de Brouwer y encontrar equilibrios de Arrow-Debreu en mercados. ^{[ 9 ]}

Fearnley, Goldberg, Hollender y Savani ^{[ 10 ]} demostraron que una clase de complejidad llamada CLS es igual a la intersección de PPAD y PLS .

Etessami y Yannakakis (quienes inventaron la clase relacionada FIXP ) ^{[ 11 ]} escriben que "El fragmento lineal a trozos de FIXP es igual a PPAD". En otras palabras, ^{[ 12 ]} los problemas en PPAD son los problemas en FIXP en los que la función de entrada es lineal a trozos.

• Equilibrios, puntos fijos y clases de complejidad: una revisión. ^{[ 13 ]}

• Encontrar el equilibrio de Nash en un juego de 2 jugadores ^{[ 3 ]} o el equilibrio épsilon en un juego con cualquier número de jugadores. ^{[ 9 ]}

• Encontrar un punto tricolor en el lema de Sperner . ^{[ 14 ]}
• Encontrar un reparto de pastel sin envidia cuando las funciones de utilidad vienen dadas por algoritmos de tiempo polinomial. ^{[ 15 ]}