Sumários

11 Dezembro 2018, 10:30 • André Souto

Resolução de exercícios da folha 9 e 10 sobre reduções e complexidade.

11 Dezembro 2018, 09:30 • André Souto

Porquê considerar polinomial eficiente.

A classe de complexidade Polinomial.

Definição formal da classe P.

Importância da classe polinomial.

Exemplos de linguagens/problemas em P.

Construção e prova de que alguns problemas estão em P.

Esquisso da prova que todos as linguagens livres de contexto estão em P.

Estudar a Secção 7.2 do Sipser

10 Dezembro 2018, 08:00 • André Souto

Resolução de exercícios da folha 9 e 10 sobre reduções e complexidade.

7 Dezembro 2018, 11:30 • André Souto

Resolução de exercícios da folha 8 e 9 sobre decidibilidade.

7 Dezembro 2018, 08:00 • André Souto

Resolução de exercícios da folha 8 e 9 sobre decidibilidade.