Seminário de Teoria da Computação
       
                 The Hitchhiker's Guide to Complexity

                      Nilton S. Volpato Filho

                 Sexta-feira, 29 de agosto de 2008

                         Sala 85  14:00hs

Neste seminário irei apresentar alguns conceitos importantes da Teoria
da Complexidade Computacional de uma maneira auto-contida e
supostamente de fácil entendimento. Veremos algumas das classes de
complexidade mais importantes, nas quais decidiu-se incluir os
problemas de maneira a classificá-los por suas dificuldades
intrínsecas. Para essas classes veremos, além de suas definições,
algumas das relações conhecidas entre elas e exemplos de problemas que
tais classes contêm.

Discutirei também sobre a maior questão da humanidade: se P = NP ou
não. A discussão será apenas filosófica. Descobri uma demonstração
verdadeiramente maravilhosa disso, no entanto essa apresentação é
curta demais para contê-la.