FL (complejidad)

En la teoría de la complejidad computacional , la clase de complejidad FL es el conjunto de problemas de funciones que pueden ser resueltos por una máquina de Turing determinista en una cantidad logarítmica de espacio de memoria . ^{[ 1 ]} Como en la definición de L , la máquina lee su entrada de una cinta de solo lectura y escribe su salida en una cinta de solo escritura; la restricción de espacio logarítmico se aplica solo a la cinta de trabajo de lectura/escritura.

En términos generales, un problema de función toma una entrada compleja y produce una salida (quizás igualmente) compleja. Los problemas de función se distinguen de los problemas de decisión , que solo producen respuestas de Sí o No. De esta manera, FL se distingue del conjunto L de problemas de decisión que pueden resolverse en el espacio logarítmico determinista. FL es un subconjunto de FP , el conjunto de problemas de función que pueden resolverse en tiempo polinomial determinista . ^{[ 1 ]}

Se sabe que FL contiene varios problemas naturales, incluyendo aritmética con números. La suma, la resta y la multiplicación de dos números usando espacio logarítmico son bastante simples, pero lograr la división es un problema mucho más complejo que estuvo abierto durante décadas. ^{[ 2 ] [ 3 ]}

De manera similar se puede definir FNL , que tiene la misma relación con NL que FNP con NP . ^{[ 1 ]}