FP (complejidad)

En la teoría de la complejidad computacional , la clase de complejidad FP es el conjunto de problemas de función que pueden ser resueltos por una máquina de Turing determinista en tiempo polinomial (y para los cuales el problema de función también representa un predicado decidible en tiempo polinomial ^{[ 1 ]} ). Es la versión de problema de función de la clase de problema de decisión P. En términos generales, es la clase de funciones que pueden ser computadas eficientemente en computadoras clásicas sin aleatorización.

La diferencia entre FP y P es que los problemas en P tienen respuestas de un bit, sí/no, mientras que los problemas en FP pueden tener cualquier salida que se pueda calcular en tiempo polinomial. Por ejemplo, sumar dos números es un problema de FP , mientras que determinar si su suma es impar pertenece a P. ^{[ 2 ]} Por lo tanto , cualquier problema de decisión en P puede considerarse como una función que produce 0 o 1, por lo que es trivialmente de FP . En resumen:${\displaystyle {\mathsf {P}}\subseteq {\mathsf {FP}}}$.

Los problemas de funciones de tiempo polinomial son fundamentales para definir las reducciones de tiempo polinomial , que a su vez se utilizan para definir la clase de problemas NP-completos . ^{[ 3 ]}

FP se define formalmente de la siguiente manera:

Una relación binaria${\displaystyle R}$está en FP si y solo si

• existe un algoritmo determinista de tiempo polinomial que, dado${\displaystyle x}$, o encuentra alguno${\displaystyle y}$de tal manera que${\displaystyle R(x,y)}$sostiene o indica que no existe tal${\displaystyle y}$existe,

• y hay un algoritmo determinista que, dado${\displaystyle x}$y${\displaystyle y}$, comprueba si${\displaystyle R(x,y)}$sostiene y se ejecuta en tiempo polinomial en el tamaño de${\displaystyle x}$.

(Esta última condición puede parecer redundante, pero se agrega para asegurar que cada problema FP esté en FNP, ya que puede haber varios${\displaystyle y}$valores para los cuales${\displaystyle R(x,y)}$se cumple, y sin la segunda condición no es necesario que el algoritmo pueda comprobar cada uno de estos valores en tiempo polinomial.)

• FNP es el conjunto de relaciones binarias R para el cual existe un algoritmo determinista que, dados x e y , comprueba si R ( x , y ) se cumple y se ejecuta en tiempo polinomial en el tamaño de x . Así como P y FP están estrechamente relacionados, NP está estrechamente relacionado con FNP . FP = FNP si y solo si P = NP .
• Dado que una máquina que utiliza espacio logarítmico tiene como máximo un número polinomial de configuraciones, FL , el conjunto de problemas de función que se pueden calcular en espacio logarítmico, está contenido en FP . Se desconoce si FL = FP ; esto es análogo al problema de determinar si las clases de decisión P y L son iguales.

• Zoológico de la complejidad: FP