Translate

1.10.12

03/10 - Márcio Moretto Ribeiro


Título: Uma introdução a complexidade computacional

O seminário desta semana será didático. O tema será Complexidade Computacional. Complexidade computacional é um tema de interesse tanto para ciência da computação quanto para lógica estando intimamente relacionado com a área de Computabilidade.
Algumas definições inicias serão apresentadas e alguns resultados clássicos como o teorema da hierarquia e o teorema de Cook serão discutidos. A apresentação focará em classes de complexidade de tempo (principalmente P e NP), classes de complexidade de espaço (NL, PSPACE etc.) não serão tratados no seminário.



2 comentários:

  1. Este comentário foi removido pelo autor.

    ResponderExcluir
    Respostas
    1. Slides do seminário: http://dl.dropbox.com/u/8818081/Seminario%20CLE%202012/np.pdf

      Excluir