A classe P
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