En la teoría de la complejidad computacional , PPA es una clase de complejidad , que significa "Argumento de paridad polinómica" (en un grafo). 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 de apretón de manos : cualquier grafo 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 un grafo 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 que está garantizado que existe (por lo tanto, tenemos un problema de búsqueda total).
PPA se define de la siguiente manera. Supongamos que tenemos un grafo cuyos vértices son cadenas binarias de -bits, y el grafo está representado por un circuito de tamaño polinomial que toma un vértice como entrada y da como salida sus vecinos. (Observe que esto nos permite representar un grafo 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 nos pide que encontremos otro vértice de grado impar. Observe que este problema está en NP: dada una solución, se puede verificar usando el circuito que la solución es correcta. Un problema de cálculo de funciones pertenece a PPA si admite una reducción en tiempo polinomial para este problema de búsqueda de grafos. Un problema está completo para la clase PPA si, además, este problema de búsqueda de grafos es reducible a ese problema.
PPAD se define de manera similar a PPA, excepto que se define en grafos dirigidos . PPAD es una subclase de PPA. Esto se debe a que el problema correspondiente que define a PPAD, conocido como END OF THE LINE, se puede reducir (de manera directa) a la búsqueda anterior de un vértice adicional de grado impar (esencialmente, simplemente ignorando las direcciones de las aristas en END OF THE LINE).
