Complexidade temporal e a classe P
30 Novembro 2021, 09:30 • André Souto
Noção de algoritmo eficiente.
Definição formal de tempo de execução numa máquina de Turing.
Relembrar a notação O-grande.
Exemplos.
Definição da classe TIME(t(n)).
Complexidade da simulação dos modelos de máquinas de Turing na máquina original.
Noção de tempo de execução numa máquina de Turing não determinista.
Complexidade da simulação da máquina não determinista na máquina original.
A classe de complexidade P e a sua importância.
Exemplos de problemas em P.