Los FPS (Cuadros por segundo)

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 problemascomputacionales 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 deTuring 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 dealeatoriedad.
A pesar del nombre de la clase, técnicamente ésta no incluye funciones, sino relaciones binarias.

Definición Formal: La diferencia entre FP y P es que estos últimos incluyen problemasque 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 dosnú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ónbinaria 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 cumpleP(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 decomplejidad 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...