Reduções entre problemas e complexidade temporal
5 Dezembro 2018, 09:30 • André Souto
Noção de redução por mapeamento entre problemas.
Noção de função computável.
Prova que se A se reduz a B e B é Turing-reconhecível (resp. decidível) então A também é Turing-reconhecível (resp. decidível).
Prova que se A se reduz a B e A é indecidível então A é indecidível.
Exemplos de uso.
Teorema de Rice.
Noção de complexidade temporal numa máquina de Turing.
Notação O-grande.
Exemplos de análise de complexidade.
Tempo de simulação de máquinas de Turing multi-fita e não deterministas em máquinas de fita simples.