En la teoría de la complejidad computacional , la clase de complejidad FL es el conjunto de problemas de función 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 desde 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 complicada y produce una salida (quizás igualmente) complicada. Los problemas de función se distinguen de los problemas de decisión , que producen solo respuestas Sí o No y corresponden al conjunto L de problemas de decisión que se pueden resolver en un espacio logarítmico determinista. FL es un subconjunto de FP , el conjunto de problemas de función que se pueden resolver en tiempo polinomial determinista . [1]
Se sabe que FL contiene varios problemas naturales, incluida la aritmética con números. La suma, la resta y la multiplicación de dos números son bastante simples, pero lograr la división es un problema mucho más profundo 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]