La complejidad de clase PPAD fue inventado por Christos Papadimitriou en su seminal 1994 de papel . La clase está diseñada para capturar la complejidad de los problemas de búsqueda en los que la existencia de una solución está garantizada por el "argumento de paridad en gráficos dirigidos": si hay un vértice desequilibrado en un gráfico dirigido, entonces debe existir otro. Pero generalmente la clase se define formalmente en términos de ( ) problema, donde el argumento se aplica solo a gráficos con ambos grados de entrada y salida . Mi pregunta es: ¿por qué son equivalentes estas nociones?
Hasta este punto, es un duplicado de esta pregunta . Ahora quiero exponer el problema formalmente y aclarar por qué no estoy satisfecho con la respuesta allí.
Problema de búsqueda ( ): se nos dan dos circuitos de tamaño polinómico y que obtienen devuelve una lista polinómica de otros elementos en . Estos circuitos definen un gráfico dirigido , donde y . El problema de búsqueda es el siguiente: dado , y tal que , encuentre otro vértice con la misma propiedad.
Problema de búsqueda : lo mismo, pero tanto como devuelven una lista vacía o un elemento.
La noción de reducibilidad (corregida según la sugerencia de Ricky): el problema de búsqueda total es reducible al problema de búsqueda total través de las funciones polinómicas y si es una solución para en el problema implica que es una solución a en el problema .
Pregunta formal : ¿por qué reducible a ? ¿O deberíamos usar otra noción de reducibilidad?
Christos Papadimitriou demuestra un teorema análogo sobre PPA (Teorema 1, página 505) pero el argumento parece no funcionar para PPAD . La razón es que un vértice con equilibrio de grados se transformará en k vértices con equilibrio de grados ± 1 . Entonces el algoritmo para A E O L puede obtener uno de estos vértices y devolver otro. Esto no sería producir un nuevo vértice para A U V .
Las cosas están empeorando porque en siempre hay un número par de vértices desequilibrados, pero en A U V puede haber un número impar de ellos. Es por eso que uno no puede construir una biyección entre estos dos conjuntos y g no podría ser siempre igual a f - 1 . Si g ( x , f ( x ) ) ≠ x obtenemos un método para resolver A U V en tiempo polinómico, al menos en algunos casos. Si g no depende de x y para y 1 ≠ y 2, entonces y 2 puede devolverse como respuesta para y 1 . Eso no sería dar una solución para una U V .
Pregunta final : ¿se pueden superar los obstáculos enumerados anteriormente? ¿Se puede emplear la posible dependencia de en x ?
fuente
Respuestas:
Se ha demostrado que los problemas son equivalentes (y, por lo tanto, PPAD completos), consulte la Sección 8 en El problema de la bola peluda es PPAD completo de Paul W. Goldberg y Alexandros Hollender .
fuente
Esta es una pregunta interesante, y solo puedo dar una respuesta parcial.
Es fácil ver que la construcción en la pág. 505 del artículo de Papadimitriou muestra la equivalencia de AUV con su caso especial
Por un lado, me resulta difícil imaginar una transformación de tales gráficos que pueda reducir una mayor cantidad de fuentes a una.
Sin embargo, por otro lado, MEOL pertenece a todas las clases comúnmente estudiadas que contienen PPAD, excepto posiblemente el propio PPAD :
Primero, obviamente,
Dibujaré a continuación un argumento que
De esta manera, producimos un gráfico no dirigido con un vértice de hoja conocido. Le pedimos al oráculo de PPA otra hoja y, por construcción, podemos extraer una respuesta para la instancia de MEOL .
(Ver esta respuesta para la equivalencia de AUV - con la definición de PPA de Papadimitriou - .)pp p
PPA - es solo PPA . Se supone que las clases PPA - son incomparables por pares, e incomparables con PPADS . Todos incluyen PPAD .p2 p
No había nada particularmente especial sobre en el argumento que describí anteriormente, y se puede modificar fácilmente para obtenerp=2
fuente