En la teoría de la complejidad computacional , la clase de complejidad TFNP es la clase de problemas de función total que se pueden resolver en tiempo polinomial no determinista. Es decir, es la clase de problemas de función que están garantizados para tener una respuesta, y esta respuesta se puede verificar en tiempo polinomial, o de manera equivalente, es el subconjunto de FNP donde se garantiza que existe una solución. La abreviatura TFNP significa "Polinomio no determinista de función total".
TFNP contiene muchos problemas naturales que interesan a los informáticos. Estos problemas incluyen la factorización de enteros , la búsqueda de un equilibrio de Nash de un juego y la búsqueda de óptimos locales. Se conjetura ampliamente que el TFNP contiene problemas que son intratables desde el punto de vista computacional, y se ha demostrado que varios de estos problemas son difíciles bajo supuestos criptográficos. [1] [2] Sin embargo, no se conocen resultados de intratabilidad incondicional o resultados que muestren la dureza NP de los problemas de TFNP. No se cree que TFNP tenga ningún problema completo. [3]
Definicion formal
La clase TFNP se define formalmente como sigue.
- 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 tanto x como y , y para cada x , existe una y que es a lo sumo polinomialmente más largo que x tal que se cumple P ( x , y ).
Fue definido por primera vez por Megiddo y Papadimitriou en 1989, [4] aunque los problemas de TFNP y las subclases de TFNP se habían definido y estudiado antes. [5]
Conexiones con otras clases de complejidad
F (NP coNP)
La clase de complejidad F (NP coNP) se puede definir de dos formas diferentes, y no se sabe que esas formas sean equivalentes. Una forma aplica F al modelo de máquina para NPcoNP. Se sabe que con esta definición, F (NPcoNP) coincide con TFNP. [4] Para ver esto, primero observe que la inclusión TFNP ⊆ F (NPcoNP) se desprende fácilmente de las definiciones de las clases. Todas las respuestas "sí" a los problemas en TFNP se pueden verificar fácilmente por definición, y dado que los problemas en TFNP son totales, no hay respuestas "no", por lo que es cierto que las respuestas "no" se pueden verificar fácilmente. Para la inclusión inversa, sea R una relación binaria en F (NPcoNP). Descomponer R en R 1 R 2 tal que (x, 0y) ∈ R 1 precisamente cuando (x, y) ∈ R y Y es una respuesta "sí", y dejar que R 2 sea (x, 1y) tales (x, y) ∈ R y y es una respuesta "no". Entonces la relación binaria R 1 ∪ R 2 está en TFNP.
La otra definición usa ese NP Se sabe que coNP es una clase de problemas de decisión de buen comportamiento y aplica F a esa clase. Con esta definición, si NP coNP = P luego F (NP coNP) = FP .
Conexión a NP
NP es una de las clases de complejidad más estudiadas. La conjetura de que existen problemas insolubles en NP es ampliamente aceptada y se utiliza a menudo como la suposición de dureza más básica. Por lo tanto, es natural preguntar cómo se relaciona TFNP con NP. No es difícil ver que las soluciones a problemas en NP pueden implicar soluciones a problemas en TFNP. Sin embargo, no hay problemas de TFNP que se sabe que son NP-hard . La intuición de este hecho proviene del hecho de que los problemas en TFNP son totales. Para que un problema sea NP-difícil, debe existir una reducción de algún problema NP-completo al problema de interés. Una reducción típica del problema Una de problemas B se lleva a cabo mediante la creación y el análisis de un mapa que envía "sí" casos de A a instancias "sí" de B y "no" los casos de A a "NO" instancias de B . Sin embargo, los problemas de TFNP son totales, por lo que no hay casos "no" para este tipo de reducción, lo que hace que las técnicas comunes sean difíciles de aplicar. Más allá de esta intuición aproximada, hay varios resultados concretos que sugieren que podría ser difícil o incluso imposible probar la dureza NP para problemas de TFNP. Por ejemplo, si cualquier problema de TFNP es NP-completo, entonces NP = coNP, [3] que generalmente se conjetura que es falso, pero sigue siendo un gran problema abierto en la teoría de la complejidad. Esta falta de conexiones con NP es una de las principales motivaciones detrás del estudio de TFNP como su propia clase independiente.
Subclases notables
La estructura de TFNP se estudia a menudo mediante el estudio de sus subclases. Estas subclases están definidas por el teorema matemático mediante el cual se garantizan las soluciones a los problemas. Un atractivo de estudiar subclases de TFNP es que, aunque se cree que TFNP no tiene ningún problema completo, estas subclases se definen por un cierto problema completo, lo que hace más fácil razonar sobre ellas.
PLS
PLS (que significa "búsqueda local polinomial") es una clase de problemas diseñados para modelar el proceso de búsqueda de un óptimo local para una función. En particular, es la clase de problemas de función total que se pueden reducir en tiempo polinómico al siguiente problema
- Dados los circuitos de entrada S y C, cada uno con n bits de entrada y salida, encuentre x tal que C (S (x)) ≤ C (X) .
Contiene la clase CLS.
PPA
PPA (que significa "Argumento de paridad de tiempo polinomial") es la clase de problemas cuya solución está garantizada por el lema del apretón de manos : cualquier gráfico no dirigido con un vértice de grado impar debe tener otro vértice de grado impar . Contiene las subclases PWPP y PPAD .
PPP
PPP (siglas de "Polynomial time Pigeonhole Principle") es la clase de problemas cuya solución está garantizada por el principio de Pigeonhole . Más precisamente, es la clase de problemas que se pueden reducir en tiempo polinomial al problema de Pigeon, definido de la siguiente manera
- Dado el circuito C con n bits de entrada y salida, encuentre x tal que C (x) = 0 o x ≠ y tal que C (x) = C (y) .
PPP contiene las clases PPAD y PWPP. Los problemas notables en esta clase incluyen el problema de la solución de números enteros cortos . [6]
PPAD
PPAD (que significa "Argumento de paridad de tiempo polinomial, dirigido") es una restricción de PPA a problemas cuyas soluciones están garantizadas por una versión dirigida del lema del apretón de manos. A menudo se define como el conjunto de problemas que son reducibles en tiempo polinómico al final de una línea:
- Circuitos Dadas S y P con n de entrada y los bits de salida S (0) ≠ 0 y P (0) = 0 , encontrar x tal que P (S (x)) ≠ x o x ≠ 0 tal que S (P (x) ) ≠ x .
PPAD está en la intersección de PPA y PPP, y contiene CLS.
CLS
CLS (que significa "Búsqueda local continua") es una clase de problemas de búsqueda diseñados para modelar el proceso de encontrar un óptimo local de una función continua sobre un dominio continuo. Se define como la clase de problemas que son reducibles en tiempo polinómico al problema de punto local continuo:
- Dadas dos funciones continuas Lipschitz S y C y los parámetros varepsilon y λ , encuentra un ε punto -approximate fijo de S con respecto a C o dos puntos que violan la λ -continuity de C o S .
Esta clase fue definida por primera vez por Daskalakis y Papadimitriou en 2011. [7] Está contenida en la intersección de PPAD y PLS, y en 2020 se ha demostrado que CLS = PPAD ∩ PLS. [8] Fue diseñado para ser una clase de problemas de optimización relativamente simples que aún contiene muchos problemas interesantes que se cree que son difíciles.
Los problemas completos para CLS son, por ejemplo, encontrar un punto ε- KKT , [9] encontrar un punto fijo ε- Banach [10] y el problema de contracción metamétrica. [11]
EOPL y UEOPL
EOPL y UEOPL (que significa "fin de línea potencial" y "fin único de línea potencial") fueron introducidos en 2020 por. [9]
UEOPL captura problemas de búsqueda que pueden resolverse mediante búsqueda local, es decir, es posible saltar de una solución candidata a la siguiente en tiempo polinomial. Además, se promete que los problemas en UEOPL tendrán una solución única. Un problema en UEOPL se puede interpretar como un gráfico acíclico dirigido exponencialmente grande donde cada nodo es una solución candidata y tiene un costo (también llamado potencial). El grado de entrada y salida de cada nodo es como máximo uno, lo que significa que los nodos forman una línea exponencialmente larga. La solución única, el nodo con el costo más alto, está al final de esa línea única. UEOPL contiene todos los problemas que se pueden reducir en tiempo polinomial al problema de búsqueda Unique-End-of-Potential-Line:
- Dados los circuitos de entrada S , P y C, cada uno con n bits de entrada y salida, S (0) ≠ 0 y P (0) = 0 , encuentre x tal que
- x es el final de la línea P (S (x)) ≠ x ,
- x es el comienzo de una segunda línea S (P (x)) ≠ x ≠ 0 ,
- x viola el costo creciente P (S (x)) = x , x ≠ S (x) y C (S (x)) - C (x) ≤ 0 o
- dos puntos x , y tales que x ≠ y, x ≠ S (x), y ≠ S (y) y C (x) = C (y) o C (x)
.
- El primer tipo de solución es el final real de la línea, mientras que las otras tres soluciones son violaciones de las propiedades que aseguran que existe una solución única. Si se viola alguna de estas propiedades, no existe una solución única. Por lo tanto, el problema es total: o se encuentra una solución única o una prueba breve de que no existe una solución única.
UEOPL contiene, entre otros, el problema de resolver la matriz P - Problema de complementariedad lineal , [9] encontrar el sumidero de una orientación de sumidero Unique en cubos, [9] resolver un juego estocástico simple [9] y el α-Ham Sandwich problema. [12] Los problemas completos de UEOPL son Unique-End-of-Potential-Line, algunas variantes con costos que aumentan exactamente en 1 o una instancia sin el circuito P , y One-Permutation-Discrete-Contraction. [9]
EOPL captura problemas de búsqueda como los de UEOPL con la relajación de que se permiten múltiples líneas y se busca cualquier final de línea. Actualmente no se conocen problemas que estén en EOPL pero no en UEOPL.
EOPL es una subclase de CLS, se desconoce si son iguales o no. UEOPL está contenido trivialmente en EOPL.
FP
FP (complejidad) (que significa "función polinomial") es la clase de problemas de función que se pueden resolver en tiempo polinomial determinista. FPCLS, y se conjetura que esta inclusión es estricta. Esta clase representa la clase de problemas de función que se cree que son manejables computacionalmente (sin aleatorización). Si TFNP = FP, entonces P = NP ∩ coNP, que debería ser intuitivo dado que TFNP = F (NPcoNP). Sin embargo, generalmente se conjetura que P ≠ NP ∩ coNP, y por lo tanto TFNP ≠ FP.
Referencias
- ^ Garg, Pandey y Srinivasan. Revisando la dureza criptográfica de encontrar un equilibrio de Nash . CRYPTO 2016.
- ^ Habàcek y Yogev. Dureza de la búsqueda local continua: complejidad de la consulta y límites inferiores criptográficos . SODA 2016.
- ^ a b Goldberg y Papadimitriou. Hacia una teoría de la complejidad unificada de las funciones totales . 2018.
- ^ a b Megiddo y Papadimitriou. Una nota sobre funciones totales, teoremas de existencia y complejidad computacional . Informática Teórica 1989.
- ^ Johnson, Papadimitriou y Yannakakis. ¿Qué tan fácil es la búsqueda local? . Revista de Ciencias de Sistemas Informáticos, 1988.
- ^ Sotiraki, Zampetakis y Zidelis. Completitud de PPP con conexiones a la criptografía . FOCS 2018
- ^ Daskalakis y Papadimitriou. Búsqueda local continua . SODA 2011.
- ^ Fearnley, John; Goldberg, Paul W .; Hollender, Alexandros; Savani, Rahul (11 de noviembre de 2020). "La complejidad del descenso del gradiente: CLS = PPAD ∩ PLS". arXiv : 2011.01929 [ cs.CC ].
- ^ a b c d e f Fearnley, John; Gordon, Spencer; Mehta, Ruta; Savani, Rahul (diciembre de 2020). "Final único de la línea potencial" . Revista de Ciencias de la Computación y Sistemas . 114 : 1-35. doi : 10.1016 / j.jcss.2020.05.007 .
- ^ Daskalakis, Constantinos; Tzamos, Christos; Zampetakis, Manolis (13 de febrero de 2018). "Un inverso al teorema del punto fijo de Banach y su integridad CLS". arXiv : 1702.07339 [ cs.CC ].
- ^ Fearnley, John; Gordon, Spencer; Mehta, Ruta; Savani, Rahul (7 de abril de 2017). "CLS: Nuevos problemas y completitud". arXiv : 1702.06017 [ cs.CC ].
- ^ Chiu, Man-Kwun; Choudhary, Aruni; Mulzer, Wolfgang (20 de marzo de 2020). "Complejidad computacional del problema α-Ham-Sandwich". arXiv : 2003.09266 [ cs.CG ].