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.

Disciplinas Execução

2024/2025 - 1 Semestre

2023/2024 - 1 Semestre