Después de mi clase de teoría de la computación de hoy, esta pregunta apareció en mi mente: si un problema puede ser resuelto por un autómata finito, este problema pertenece a P.
Creo que es cierto, ya que los autómatas reconocen lenguajes muy simples, por lo tanto, todos estos lenguajes tendrían algoritmos polinómicos para resolverlos. Entonces, ¿es cierto que cualquier problema resuelto por un autómata finito está en P?
Si es cierto. En términos de clases de complejidad, donde es la clase de lenguajes regulares (es decir, problemas que pueden ser resueltos por un autómata finito). Más específicamente, y es un subconjunto estricto de por el teorema de la jerarquía de tiempo.
La prueba de (*) es la siguiente: para cualquier problema en , hay un DFA que lo resuelve. Convierta ese DFA en una máquina Turing con los mismos estados y función de transición, que siempre se mueve hacia la derecha hasta que vea un espacio en blanco, y luego acepta o rechaza. Esta máquina de Turing siempre se detiene a tiempo exactamente .
También vale la pena mencionar que para cualquier constante fija .
Sí, es cierto. Para cada uno de estos problemas existe un DFA que decide el idioma, y la comprobación de si una palabra es aceptada por un DFA puede hacerse fácilmente en un tiempo lineal en la longitud de la palabra.