Após minha aula de Teoria da Computação hoje, essa pergunta surgiu em minha mente: se um problema pode ser resolvido por um autômato finito, esse problema pertence a P.
Eu acho que é verdade, já que os autômatos reconhecem linguagens muito simples, portanto todas essas linguagens teriam algoritmos polinomiais para resolvê-las. Assim, é verdade que qualquer problema resolvido por um autômato finito está em P?
Sim, é verdade. Em termos de classes de complexidade, que é a classe de linguagens regulares (ou seja, problemas que podem ser resolvidos por um autômato finito). Mais especificamente, e é um subconjunto estrito de pelo teorema da hierarquia de tempo.
A prova de (*) é a seguinte: para qualquer problema em , existe um DFA que o resolve. Converta esse DFA em uma máquina de Turing com os mesmos estados e função de transição, que sempre se move para a direita até ver um espaço em branco e, em seguida, aceita ou rejeita. Essa máquina de Turing sempre pára no tempo exatamente .
Também vale a pena mencionar que para qualquer constante fixa .
Sim isso é verdade. Para cada um desses problemas, existe um DFA que decide o idioma, e verificar se uma palavra é aceita por um DFA pode ser facilmente realizado em tempo linear no comprimento da palavra.