PPA (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 la aplicación del lema de apretón de manos : 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 que está garantizado para existir (entonces, tenemos un problema de búsqueda total ).
PPA se define de la siguiente manera. Suponga que tenemos una gráfica en cuyos vértices hay cadenas binarias de -bit, y la gráfica está representada por un circuito del tamaño de un polinomio que toma un vértice como entrada y da salida a sus vecinos. (Tenga en cuenta que esto nos permite representar una gráfica exponencialmente grande en la que podemos realizar una exploración local de manera eficiente). Suponga además que un vértice específico (digamos el vector de todos ceros) tiene un número impar de vecinos. Estamos obligados a encontrar otro vértice de grado impar. Tenga en cuenta que este problema está en NP; dada una solución, se puede verificar mediante 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 en este problema de búsqueda de gráficos. Un problema esta completo para la clase PPA si además, este problema de búsqueda de gráficos se puede reducir a ese problema.
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 FIN DE LA LÍNEA, se puede reducir (de una manera sencilla) a la búsqueda anterior de un vértice de grado impar adicional (esencialmente, simplemente ignorando las direcciones de los bordes en END DE LA LÍNEA).