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 . Es la versión problema función del problema de decisión de clase P . En términos generales, es la clase de funciones que se pueden calcular de manera eficiente 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, la adición de dos números es una FP problema, mientras que la determinación de si su suma es impar es en P . [1]
Los problemas de función de tiempo polinómico son fundamentales para definir reducciones de tiempo polinómico , que se utilizan a su vez para definir la clase de problemas NP completos . [2]
Definicion formal
FP se define formalmente de la siguiente manera:
- Una relación binariaestá en FP si y solo si hay un algoritmo de tiempo polinomial determinista que, dado , puedo encontrar algunos tal que sostiene.
Clases de complejidad relacionadas
- FNP es el conjunto de relaciones binarias para las que no es un algoritmo de tiempo polinómico que, dadas x y y , comprueba si P ( x , y ) se mantiene. Así como P y FP están estrechamente relacionados, NP está estrechamente relacionado con FNP . FP = FNP si y solo si P = NP .
- Debido a que una máquina que usa espacio logarítmico tiene como mucho polinomialmente muchas configuraciones, FL , el conjunto de problemas de función que se pueden calcular en el espacio de registro, está contenido en FP . No se sabe si FL = FP ; esto es análogo al problema de determinar si las clases de decisión P y L son iguales.
Referencias
- ^ Bürgisser, Peter (2000). Completitud y reducción en la teoría de la complejidad algebraica . Algoritmos y Computación en Matemáticas. 7 . Berlín: Springer-Verlag . pag. 66. ISBN 3-540-66752-0. Zbl 0948.68082 .
- ^ Rich, Elaine (2008). "28.10" Las clases de problemas FP y FNP " ". Autómatas, computabilidad y complejidad: teoría y aplicaciones . Prentice Hall. págs. 689–694. ISBN 0-13-228806-0.