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.
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 FNPsi 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
Datos:Q970152
Junio 27, 2022
clase, complejidad, complejidad, computacional, function, funcional, clase, complejidad, extiende, clase, cual, incluye, exclusivamente, problemas, decisión, hacia, problemas, computacionales, tipo, funcional, decir, aquellos, obtienen, como, salidas, valores,. 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 decision hacia problemas computacionales de tipo funcional es decir aquellos que obtienen como salidas valores distintos de SI o NO Es decir corresponde al conjunto de problemas funcionales que pueden ser resueltos por una Maquina de Turing determinista en tiempo polinomial lo cual en la practica significa que incluye a todos los problemas que pueden ser resueltos eficientemente en los computadores clasicos sin necesidad de aleatoriedad A pesar del nombre de la clase tecnicamente esta no incluye funciones sino relaciones binarias Definicion formal EditarUna relacion binaria P x y esta en FP si y solo si existe un algoritmo determinista que dada una entrada x puede encontrar algun y en tiempo polinomial tal que se cumpla P x y La diferencia entre FP y P es que estos ultimos incluyen problemas que poseen como salida un unico bit que significa una respuesta SI o NO mientras que los primeros pueden tener cualquier salida que pueda ser computada en un tiempo polinomial Por ejemplo sumar dos numeros es un problema FP mientras que determinar si su suma es par es un problema P Mas compleja es la relacion entre FP la clase FNP la cual se define de la siguiente manera Una relacion binaria P x y donde y es a lo mas polinomialmente mas grande que x esta en FNP si y solo 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 solo 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 tambien muestra que FP esta contenida en FNP y que de hecho FP FNP si y solo si P NP Los problemas FP son fundamentales en la definicion de reducciones polinomiales las que son usadas para incluir problemas en la clase de los NP completos Como una maquina que utiliza espacio logaritmico tiene a lo mas un numero polinomial de configuraciones la clase FL el conjunto de problemas funcionales que pueden ser calculados en espacio logaritmico esta contenida en FP Se desconoce si FL FP una pregunta analoga a la de determinar si las clases de problemas de decision P y L son iguales Referencias EditarElaine Rich Automata computability and complexity theory and applications Prentice Hall 2008 ISBN 0132288060 section 28 10 The problem classes FP and FNP pp 689 694Enlaces externos EditarComplexity Zoo FP Datos Q970152 Obtenido de https es wikipedia org w index php title FP clase de complejidad amp oldid 119640147, wikipedia, wiki, leyendo, leer, libro, biblioteca,
