Disciplina Curricular
Complexidade Computacional CC
Mestrado Bolonha em Matemática - 2_MMat 2022/23
Contextos
Grupo: 2_MMat 2022/23 > 2º Ciclo > Parte Escolar > Opcionais > 2º Ano > 689_Opcionais Área CMat / 2º Ano
Período:
Grupo: 2_MMat 2022/23 > 2º Ciclo > Parte Escolar > Opcionais > 1º Ano > 688_Opcionais Área CMat / 1º Ano > 1º Semestre
Período:
Peso
6.0 (para cálculo da média)
Objectivos
O curso oferecerá uma introdução intensa ao campo da Complexidade Computacional. O curso será organizado historicamente, abrangendo desde o início da área, até o início dos anos 2000.
Programa
Parte 1 - Classes de Complexidade e Diagonalização * A invenção do computador: máquinas de Turing e o problema da paragem * Medidas de complexidade e Máquinas de Acesso Aleatório * Teoremas de hierarquia * A carta perdida de Gödel, reduções, teorema de Cook-Levin, P vs NP * Complexidade de espaço: L vs NL vs P vs PSPACE * A barreira da relativização Parte 2 - A abordagem combinatória * Modelos combinatórios: Circuitos Booleanos, limites inferiores, redução de profundidade * Computação randomizada: ZPP, RP, BPP, desrandomização, dureza vs aleatoriedade * Algoritmos e limites inferiores para circuitos de profundidade constante * A fronteira nos limites inferiores de circuitos: Circuitos de profundidade constante com portas modulares * Complexidade da comunicação e o teorema de Karchmer-Wigderson * Alguns limites inferiores em complexidade da comunicação * A barreira das provas naturais Parte 3 - Outros tópicos (apresentações dos alunos)
Métodos de ensino e avaliação
A avaliação é feita por testes ou exame, com a possibilidade de fazer uma apresentação sobre um tema de Complexidade Computacional, à escolha do aluno.