Dejemos que $M$ sea una máquina de Turing no determinista que reconoce un lenguaje $L$ es decir, para cada palabra de entrada $u$ hay un cálculo de aceptación con entrada $u$ si y sólo si $u\in L$ . El tiempo más pequeño de dicho cálculo se denota $T_M(u)$ . Para cada $n\ge 1$ definimos $T_M(n)$ el máximo de todos los $T_M(u)$ para todos los aceptados $u$ de longitud $\le n$ . Entonces $T_M(n)\colon \mathbb{N}\to \mathbb{N}$ es la función temporal de $M$ .
Pregunta. ¿Se pueden caracterizar todas las funciones temporales de las máquinas de Turing no deterministas, por ejemplo, en términos de la complejidad temporal de calcular sus valores?
Actualización Las funciones de tiempo de las máquinas de Turing deterministas son tiempo-construible . Dado que existe una ralentización exponencial al pasar de una TM no determinista a una determinista, existe una restricción similar para la función de tiempo no determinista. La cuestión es: cuál es la restricción "correcta".
