TFNP

• Entrada : Una función f (computable polinómicamente) que asigna un conjunto de n  +  1 elementos a un conjunto de n elementos.
• Pregunta : Encuentra dos elementos a y b tales que f ( a )  = f ( b ). 

Sea x una función y y una tupla de 2 elementos en su dominio. La relación binaria en cuestión P ( x , y ) significa "las imágenes de ambas entradas de y bajo x son iguales", lo cual, dado que la función es computable polinómicamente, es decidible polinómicamente. Además, dicha tupla y debe existir para cualquier función debido al principio del palomar .

La clase de complejidad${\displaystyle {\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})}$se puede definir de dos maneras diferentes, y no se sabe si esas maneras son equivalentes. Una manera aplica F al modelo de máquina para${\displaystyle {\mathsf {NP}}\cap {\mathsf {coNP}}}$. Se sabe que con esta definición,${\displaystyle {\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})}$coincide con TFNP. ^{[ 4 ]} Para ver esto, primero observe que la inclusión${\displaystyle {\mathsf {TFNP}}\subseteq {\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})}$Se deduce 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 trivialmente cierto que las respuestas "no" se pueden verificar fácilmente. Para la inclusión inversa, sea R una relación binaria en${\displaystyle {\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})}$. Descomponer R en${\displaystyle R_{1}\cup R_{2}}$de tal manera que${\displaystyle (x,0y)\in R_{1}}$precisamente cuando${\displaystyle (x,y)\in R}$y sea y una respuesta "sí", y sea R ₂ ⁠${\displaystyle (x,1y)}$tal​ ​${\displaystyle (x,y)\in R}$y es una respuesta "no". Entonces la relaciónbinaria${\displaystyle R_{1}\cup R_{2}}$está en TFNP.

La otra definición utiliza eso${\displaystyle {\mathsf {NP}}\cap {\mathsf {coNP}}}$Se sabe que es una clase de problemas de decisión bien comportada y aplica F a esa clase. Con esta definición, si${\displaystyle {\mathsf {NP}}\cap {\mathsf {coNP}}={\mathsf {P}}}$entonces${\displaystyle {\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})={\mathsf {\color {Blue}FP}}}$.

NP es una de las clases de complejidad más estudiadas. La conjetura de que existen problemas intratables en NP es ampliamente aceptada y se utiliza a menudo como la suposición de dificultad más básica. Por lo tanto, es natural preguntarse 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 se conocen problemas de TFNP que sean NP-difíciles . La intuición para 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 A al problema B se realiza creando y analizando un mapa que envía instancias "sí" de A a instancias "sí" de B e instancias "no" de A a instancias "no" de B. Sin embargo, los problemas de TFNP son totales, por lo que no hay instancias "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 general, existen varios resultados concretos que sugieren que podría ser difícil, o incluso imposible, demostrar la NP-dificultad de los problemas TFNP. Por ejemplo, si algún problema TFNP es NP-completo, entonces NP = coNP, ^{[ 3 ]} lo cual generalmente se conjetura como falso, pero sigue siendo un importante problema abierto en la teoría de la complejidad. Esta falta de conexiones con NP es una motivación importante para el estudio de TFNP como una clase independiente.

PLS (acrónimo de "Polynomial Local Search") 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 polinomial al siguiente problema.

Dados los circuitos de entrada S y C, cada uno con n bits de entrada y salida, encuentre x tal que${\displaystyle C(S(x))\leq C(X)}$⁠ .

Contiene la clase CLS.

PPA (acrónimo de "Polynomial time Parity Argument") es la clase de problemas cuya solución está garantizada por el lema de intercambio de claves : cualquier grafo no dirigido con un vértice de grado impar debe tener otro vértice de grado impar . Contiene la subclase PPAD . Entre los problemas notables PPA-completos se incluye LONELY: dado un circuito que define un emparejamiento parcial en ${\displaystyle \{0,1\}^{n}}$de tal manera que${\displaystyle {\vec {0}}}$Si no hay coincidencia, busque otro vértice que no tenga coincidencia. ^{[ 6 ]}

PPP (acrónimo de "Principio del Palomar en Tiempo Polinomial") es la clase de problemas cuya solución está garantizada por el principio del palomar . Más precisamente, es la clase de problemas que pueden reducirse en tiempo polinomial al problema del palomar, definido de la siguiente manera:

Dado el circuito C con n bits de entrada y salida, encuentre x tal que${\displaystyle C(x)=0}$o x ≠ y tal que​${\displaystyle C(x)=C(y)}$⁠ .

PPP contiene las clases PPAD y PWPP. Entre los problemas notables de esta clase se incluye el problema de la solución entera corta . ^{[ 7 ]}

PPAD (que significa "Argumento de paridad en 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 polinomial a End-of-a-Line:

Dados los circuitos S y P con n bits de entrada y salida .${\displaystyle S(0)\neq 0}$y​​${\displaystyle P(0)=0}$, encuentra x tal que${\displaystyle P(S(x))\neq x}$o​​${\displaystyle x\neq 0}$de tal manera que${\displaystyle S(P(x))\neq x}$⁠ .

PPAD se encuentra en la intersección de PPA y PPP, y contiene CLS.

Aquí, el circuito S en la definición envía cada punto de la línea a su sucesor, o a sí mismo si el punto es un sumidero. De igual manera, P envía cada punto de la línea a su predecesor, o a sí mismo si el punto es una fuente. Los puntos fuera de todas las líneas se identifican al estar fijos bajo P y S (en otras palabras, cualquier punto aislado se elimina del gráfico). Entonces la condición${\displaystyle P(S(x))\neq x}$define el final de una línea, que es un sumidero o es tal que S ( x ) = S ( y ) para algún otro punto y ; de manera similar , la condición${\displaystyle S(P(x))\neq x}$define el comienzo de una línea (ya que asumimos que 0 es una fuente, requerimos que la solución sea distinta de cero en este caso).

La búsqueda local continua (CLS) 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 se pueden reducir en tiempo polinomial al problema del punto local continuo:

Dadas dos funciones continuas de Lipschitz S y C y parámetros ε y λ , encuentre un punto fijo ε -aproximado de S con respecto a C o dos puntos que violen la λ -continuidad de C o S.

Esta clase fue definida por primera vez por Daskalakis y Papadimitriou en 2011. ^{[ 8 ]} Está contenida en la intersección de PPAD y PLS, y en 2020 se ha demostrado que${\displaystyle {\mathsf {CLS}}={\mathsf {PPAD}}\cap {\mathsf {PLS}}}$. ^{[ 9 ] [ 10 ]} Fue diseñado para ser una clase de problemas de optimización relativamente simples que aún contiene muchos problemas interesantes que se consideran difíciles.

Los problemas completos para CLS son, por ejemplo, encontrar un punto ε- KKT , ^{[ 11 ]} encontrar un punto fijo ε-Banach ^{[ 12 ]} y el problema de la contracción metamétrica. ^{[ 13 ]}

EOPL y UEOPL (que significan "fin de línea potencial" y "fin único de línea potencial") fueron introducidos en 2020 por. ^{[ 11 ]}

EOPL 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. Un problema en EOPL puede interpretarse como un grafo acíclico, dirigido y exponencialmente grande, donde cada nodo es una solución candidata y tiene un costo (también llamado potencial) que aumenta a lo largo de las aristas. El grado de entrada y salida de cada nodo es como máximo uno, lo que significa que los nodos forman una colección de líneas exponencialmente largas. El final de cada línea es el nodo con el costo más alto en esa línea. EOPL contiene todos los problemas que pueden reducirse en tiempo polinomial al problema de búsqueda End-of-Potential-Line:

Dados los circuitos de entrada S y P , cada uno con n bits de entrada y salida, y C con n bits de entrada y m bits de salida,${\displaystyle S(0)\neq 0}$,​​${\displaystyle P(0)=0}$y​​${\displaystyle C(0)=0}$⁠ , encuentra x tal que

• x es el final de la línea${\displaystyle P(S(x))\neq x}$⁠ ,
• x es el inicio de una segunda línea${\displaystyle S(P(x))\neq x\neq 0}$, o
• x viola el costo creciente${\displaystyle P(S(x))=x}$,​​${\displaystyle x\neq S(x)}$y​​${\displaystyle C(S(x))-C(x)\leq 0}$⁠

Aquí, S envía cada vértice del grafo a su sucesor, o a sí mismo si el vértice es un sumidero. De igual manera, P envía cada vértice del grafo a su predecesor, o a sí mismo. Los puntos fuera del grafo se identifican al estar fijos tanto bajo P como bajo S. Entonces, el primer y segundo tipo de solución son, respectivamente, los extremos superior e inferior de la línea, y el tercer tipo de solución es una violación de la condición de que el potencial aumenta a lo largo de las aristas. Si se viola esta última condición, el punto final puede no maximizar el potencial en la línea. Por lo tanto, el problema es total: o se encuentra una solución o se encuentra una breve demostración de que las condiciones no se cumplen.

UEOPL se define de forma muy similar, pero se garantiza que solo hay una línea. Por lo tanto, encontrar el segundo tipo de solución mencionado anteriormente violaría la promesa que asegura que el primer tipo de solución es único. Se agrega un cuarto tipo de solución para proporcionar otra forma de detectar la presencia de una segunda línea:

• dos puntos x , y tales que${\displaystyle x\neq y,x\neq S(x),y\neq S(y)}$y cualquiera de las dos${\displaystyle C(x)=C(y)}$o​​${\displaystyle C(x)<C(y)<C(S(x))}$⁠ .

Una solución de este tipo indica que x e y se encuentran en líneas diferentes, o bien que se incumple la condición de que los valores en la misma línea sean estrictamente crecientes. La ventaja de incluir esta condición radica en que puede resultar más sencillo hallar x e y según lo requerido que encontrar el inicio de sus respectivas líneas, o bien detectar un incumplimiento explícito de la condición de costo creciente.

UEOPL contiene, entre otros, el problema de resolver el problema de complementariedad lineal de la matriz P , ^{[ 11 ]} encontrar el sumidero de una orientación de sumidero única en cubos, ^{[ 11 ]} resolver un juego estocástico simple ^{[ 11 ]} y el problema del sándwich de jamón α. ^{[ 14 ]} Los problemas completos de UEOPL son Unique-End-of-Potential-Line, algunas variantes del mismo con costos que aumentan exactamente en 1 o una instancia sin el circuito P , y One-Permutation-Discrete-Contraction. ^{[ 11 ]}

EOPL aborda problemas de búsqueda similares a los de UEOPL, con la diferencia de que se permiten varias líneas y se busca en cualquier extremo de una línea. Actualmente no se conocen problemas que estén presentes en EOPL pero no en UEOPL.

EOPL es una subclase de CLS; se desconoce si son iguales o no. UEOPL está trivialmente contenido en EOPL.

FP (acrónimo de "Function Polynomial", que significa "Polinomio de Función") es la clase de problemas de funciones que se pueden resolver en tiempo polinomial determinista. ${\displaystyle {\mathsf {FP}}\subseteq {\mathsf {CLS}}}$y se conjetura que esta inclusión es estricta. Esta clase representa la clase de problemas de función que se consideran computacionalmente tratables (sin aleatorización). Si TFNP = FP, entonces${\displaystyle {\mathsf {P}}={\mathsf {NP}}\cap {\mathsf {coNP}}}$⁠ , lo cual debería ser intuitivo dado el hecho de que ⁠${\displaystyle {\mathsf {TFNP}}={\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})}$Sin embargo, generalmente se conjetura que${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}\cap {\mathsf {coNP}}}$y por lo tanto TFNP ≠ FP.