Classe P

Questões-guia:

1. Porque problemas que podem ser resolvidos em tempo polinomial são considerados "tratáveis"?  Dê três motivos.
2. O que é um problema abstrato?
3. Para que servem codificações?
4. Defina alguns conceitos básicos da teoria de linguagens formais: alfabeto, linguagem, string vazia, linguagem vazia, operações sobre linguagens (união, intersecção, complemento, concatenação).
5. O que é o fecho de uma linguagem L, denotado por L*?
6. O que significa dizer que uma string s é aceita por um algoritmo A?  E o que é s ser rejeitada por A?
7. O que significa dizer que uma linguagem L é aceita por um algoritmo A?  E o que é L ser decidida por A?
8. O que significa dizer que uma linguagem L é aceita (decidida) por um algoritmo A em tempo polinomial?
9. Defina a classe P.

Exercícios:

1. Exercício 34.1-1 do Cormen.
2. Dê uma versão de decisão para o problema de achar uma árvore espalhada mínima num grafo não orientado ponderado.
3. Mostre que se uma linguagem L está em P, então L* também está em P.