PPA (complejidad)

Clase de complejidad

En la teoría de la complejidad computacional , PPA es una clase de complejidad que significa "Argumento de paridad polinomial" (en un gráfico). Introducido por Christos Papadimitriou en 1994 ^[1] (página 528), PPA es una subclase de TFNP . Es una clase de problemas de búsqueda que se puede demostrar que son totales mediante una aplicación del lema del protocolo de enlace : cualquier gráfico no dirigido que tenga un vértice cuyo grado sea un número impar debe tener algún otro vértice cuyo grado sea un número impar . Esta observación significa que si se nos da una gráfica y un vértice de grado impar, y se nos pide que encontremos algún otro vértice de grado impar, entonces estamos buscando algo cuya existencia está garantizada (por lo tanto, tenemos un problema de búsqueda total). ).

Definición

PPA se define de la siguiente manera. Supongamos que tenemos un gráfico en cuyos vértices hay cadenas binarias de bits, y el gráfico está representado por un circuito de tamaño polinomial que toma un vértice como entrada y genera sus vecinos. (Tenga en cuenta que esto nos permite representar un gráfico exponencialmente grande en el que podemos realizar una exploración local de manera eficiente). Supongamos además que un vértice específico (por ejemplo, el vector de todos ceros) tiene un número impar de vecinos. Se requiere encontrar otro vértice de grado impar. Tenga en cuenta que este problema está en NP; dada una solución, se puede verificar utilizando el circuito que la solución es correcta. Un problema de cálculo de funciones pertenece a PPA si admite una reducción de tiempo polinomial a este problema de búsqueda de gráficos. Un problema es completo para la clase PPA si además, este problema de búsqueda de gráficos es reducible a ese problema. ${\displaystyle n}$

Clases relacionadas

PPAD se define de manera similar a PPA, excepto que se define en gráficos dirigidos . PPAD es una subclase de PPA. Esto se debe a que el problema correspondiente que define PPAD, conocido como FINAL DE LA LÍNEA, se puede reducir (de forma sencilla) a la búsqueda anterior de un vértice adicional de grado impar (esencialmente, simplemente ignorando las direcciones de los bordes en FINAL). DE LA LÍNEA).

Ejemplos

• Existe una versión no orientada del lema de Sperner que se sabe que es completa para PPA. ^[2]
• Se sabe que el problema de la reducción del consenso a la mitad es total para la PPA. ^[3]
• El problema de buscar un segundo ciclo hamiltoniano en un gráfico de 3 regulares es miembro de PPA, pero no se sabe que esté completo para PPA.
• Hay una reducción aleatoria del tiempo polinomial del problema de factorización de números enteros a problemas completos para PPA. ^[4]

Referencias

1. Cristos Papadimitriou (1994). «Sobre la complejidad del argumento de la paridad y otras pruebas de existencia ineficientes» (PDF) . Revista de Ciencias de la Computación y de Sistemas . 48 (3): 498–532. doi :10.1016/S0022-0000(05)80063-7. Archivado desde el original (PDF) el 4 de marzo de 2016 . Consultado el 19 de diciembre de 2009 .
2. Miguel Ángel Grigni (1995). "Un lema de Sperner completo para PPA". Cartas de procesamiento de información . 77 (5–6): 255–259. CiteSeerX 10.1.1.63.9463 . doi :10.1016/S0020-0190(00)00152-6. 
3. A. Filos-Ratsikas; PW Goldberg (2018). "La reducción del consenso a la mitad es un PPA completo". Proc. del 50º Simposio de Teoría de la Computación . págs. 51–64. arXiv : 1711.04503 . doi :10.1145/3188745.3188880.
4. E. Jeřábek (2016). "Factorización de enteros y raíces cuadradas modulares". Revista de Ciencias de la Computación y de Sistemas . 82 (2): 380–394. arXiv : 1207.5220 . doi :10.1016/j.jcss.2015.08.001.