FP (clase de complejidad)
From Wikipedia, the free encyclopedia
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.
