stringtranslate.com

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 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 de juegos algorítmicos 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 luego Chen y Deng lo extendieron a 2 jugadores. [3] [4]

Definición

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:

Una relación binaria P( x , y ) está en TFNP si y solo si hay un algoritmo de tiempo polinomial determinista que puede determinar si P( x , y ) se cumple dados x e y , y para cada x , existe una 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 una 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 exponencialmente grande) en el que cada vértice tiene como máximo un predecesor y como máximo un sucesor. G se especifica dando una función computable en tiempo polinomial f( v ) (polinomio del 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, encuentre 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 .

Si existe un s , debe existir un t de este tipo , ya que la estructura de G implica que los vértices con un solo vecino se presentan en pares. En particular, dado s , podemos encontrar un t de este tipo en el otro extremo de la cadena a partir de s . (Tenga en cuenta que esto puede llevar un tiempo exponencial si solo evaluamos f repetidamente).

Relaciones con otras clases de complejidad

PPAD está contenido en (pero no se sabe si es igual a) PPA (la clase correspondiente de argumentos de paridad para gráficos no dirigidos ) que está contenida en TFNP. PPAD también está contenido en (pero no se sabe si es 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 PPAD-completitud es una evidencia más débil de intratabilidad que la de 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 de los problemas PPAD es siempre sí, ya que se sabe que existe una solución, aunque pueda ser difícil encontrarla. [6] Sin embargo, PPAD y NP están estrechamente relacionados. Si bien la pregunta sobre si existe un equilibrio de Nash para un juego dado no puede ser NP-difícil porque la respuesta siempre es sí, la pregunta sobre si existe un segundo equilibrio es NP completa. [7] Algunos ejemplos de problemas PPAD-completos incluyen la búsqueda de equilibrios de Nash , el cálculo de puntos fijos en funciones de Brouwer y la búsqueda de equilibrios de Arrow-Debreu en mercados. [8]

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

Lectura adicional

Otros problemas completos notables

Referencias

  1. ^ Christos Papadimitriou (1994). "Sobre la complejidad del argumento de la paridad y otras pruebas ineficientes de existencia" (PDF) . Journal of Computer and System Sciences . 48 (3): 498–532. doi :10.1016/S0022-0000(05)80063-7. Archivado desde el original (PDF) el 2016-03-04 . Consultado el 2008-03-08 .
  2. ^ Fortnow, Lance (2005). "¿Qué es PPAD?" . Consultado el 29 de enero de 2007 .
  3. ^ ab * Chen, Xi; Deng, Xiaotie (2006). Solución de la complejidad del equilibrio de Nash entre dos jugadores . Proc. 47.° Simposio Fundamentos de la ciencia informática. págs. 261–271. doi :10.1109/FOCS.2006.69. ECCC  TR05-140..
  4. ^ Daskalakis, Constantinos.; Goldberg, Paul W.; Papadimitriou, Christos H. (1 de enero de 2009). "La complejidad de calcular un equilibrio de Nash". Revista SIAM de Computación . 39 (1): 195–259. CiteSeerX 10.1.1.152.7003 . doi : 10.1137/070699652. ISSN  0097-5397. 
  5. ^ Daskalakis, C.; Papadimitriou, C. (23 de enero de 2011). Búsqueda local continua . Actas. Sociedad de Matemática Industrial y Aplicada. págs. 790–804. CiteSeerX 10.1.1.362.9554 . doi :10.1137/1.9781611973082.62. ISBN  9780898719932.S2CID2056144  .​
  6. ^ Scott Aaronson (2011). "Por qué los filósofos deberían preocuparse por la complejidad computacional". arXiv : 1108.1791 [cs.CC].
  7. ^ Christos Papadimitriou (2011). "Conferencia: La complejidad de encontrar un equilibrio de Nash" (PDF) .
  8. ^ ab C. Daskalakis, PW Goldberg y CH Papadimitriou (2009). "La complejidad de calcular un equilibrio de Nash". Revista SIAM de Computación . 39 (3): 195–259. CiteSeerX 10.1.1.152.7003 . doi : 10.1137/070699652. 
  9. ^ Fearnley, John; Goldberg, Paul; Hollender, Alexandros; Savani, Rahul (19 de diciembre de 2022). "La complejidad del descenso de gradiente: CLS = PPAD ∩ PLS". Revista de la ACM . 70 (1): 7:1–7:74. arXiv : 2011.01929 . doi :10.1145/3568163. ISSN  0004-5411. S2CID  263706261.
  10. ^ Yannakakis, Mihalis (1 de mayo de 2009). "Equilibrios, puntos fijos y clases de complejidad". Computer Science Review . 3 (2): 71–85. arXiv : 0802.2831 . doi :10.1016/j.cosrev.2009.03.004. ISSN  1574-0137.
  11. ^ Xi Chen y Xiaotie Deng (2006). "Sobre la complejidad del problema de punto fijo discreto en 2D". Coloquio internacional sobre autómatas, lenguajes y programación . pp. 489–500. ECCC  TR06-037.
  12. ^ Deng, X.; Qi, Q.; Saberi, A. (2012). "Soluciones algorítmicas para cortar pasteles sin envidia". Investigación de operaciones . 60 (6): 1461. doi :10.1287/opre.1120.1116. S2CID  4430655.