Listas de exercícios

1. Lista 1 [ps] [pdf]: máquinas de Turing.
2. Lista 2 [ps] [pdf]: máquinas de Turing não-determinísticas.
3. Lista 3 [ps] [pdf]: indecidibilidade, linguagens recursivas e recursivamente enumeráveis.
4. Lista 4 [ps] [pdf]: as classes P e NP, reduções, fechamento, completude.
5. Lista 5: reduções, problemas NP-completos e suas variantes.
6. Lista 6: coNP, PRIMES, algoritmos probabilísticos e cripto.