FP (clase de complejidad)

En complejidad computacional, FP ("function P" o "P funcional") es la clase de complejidad que extiende la clase P (la cual incluye exclusivamente problemas de decisión), hacia problemas computacionales de tipo funcional, es decir, aquellos que obtienen como salidas valores distintos de SÍ o NO. Es decir, corresponde al conjunto de problemas funcionales que pueden ser resueltos por una Máquina de Turing determinista en tiempo polinomial, lo cual en la práctica significa que incluye a todos los problemas que pueden ser resueltos eficientemente en los computadores clásicos, sin necesidad de aleatoriedad.

A pesar del nombre de la clase, técnicamente ésta no incluye funciones, sino relaciones binarias.

Definición formal

Una relación binaria P(x,y) está en FP si y sólo si existe un algoritmo determinista que dada una entrada x, puede encontrar algún y en tiempo polinomial tal que se cumpla P(x,y).

La diferencia entre FP y P es que estos últimos incluyen problemas que poseen como salida un único bit, que significa una respuesta SÍ o NO, mientras que los primeros pueden tener cualquier salida que pueda ser computada en un tiempo polinomial. Por ejemplo, sumar dos números es un problema FP, mientras que determinar si su suma es par es un problema P.

Más compleja es la relación entre FP la clase FNP, la cual se define de la siguiente manera:

Una relación binaria P(x,y), donde y es a lo más polinomialmente más grande que x, está en FNP si y sólo si existe un algoritmo determinista que puede determinar en tiempo polinomial si, dados x e y, se cumple P(x,y).

Esto significa que en lugar de sólo verificar y, un algoritmo para resolver un problema FP debe encontrar dicho valor. La diferencia entre FP y FNP es similar a la existente entre las clases de complejidad P y NP. Esto también muestra que FP está contenida en FNP, y que de hecho, FP = FNP si y sólo si P = NP.

Los problemas FP son fundamentales en la definición de reducciones polinomiales, las que son usadas para incluir problemas en la clase de los NP-completos.

Como una máquina que utiliza espacio logarítmico tiene a lo más un número polinomial de configuraciones, la clase FL, el conjunto de problemas funcionales que pueden ser calculados en espacio logarítmico, está contenida en FP. Se desconoce si FL = FP, una pregunta análoga a la de determinar si las clases de problemas de decisión P y L son iguales.

Referencias

• Elaine Rich, Automata, computability and complexity: theory and applications, Prentice Hall, 2008, ISBN 0132288060, section 28.10 "The problem classes FP and FNP", pp. 689-694

Enlaces externos

• Complexity Zoo: FP

• Datos: Q970152