Objetivos e enquadramento
Nesta unidade curricular pretende-se expôr aos alunos técnicas que provem ou sugiram que não existem métodos eficientes para resolver alguns problemas importantes em Ciência de Computadores com impacto na vida real (nomeadamente a factorização). Neste sentido é feito um estudo teórico de várias classes de complexidade e das relações entre elas, tais como: P, NP, co-NP, PSPACE, EXP, L, NL, PH, RP, BPP, e IP. Ênfase especial será dada ao papel da aleatoridade no desempenho de vários algoritmos.
Programa
- Motivação e Revisões. Reconhecer o papel da Complexidade Computacional como área científica da Ciência de Computadores. Saber a definição de máquina de Turing. Definir problemas decidíveis, semidecidíveis e não decidíveis.
- Classes de Complexidade e teoremas de hierarquia.
- As classes P e NP. Definir as classes de complexidade P e NP usando máquinas de Turing e como um problema de procura. Problemas completos para uma classe. Conhecer as propriedades das classes P, NP, co-NP e NP-c. Interpretar a questão P vs NP.
- A Hierarquia Polinomial e a classe PSPACE. Definir máquinas de Turing com acesso a um oráculo. Definir a hierarquia polinomial (PH) via máquinas de Turing com oráculo e via quantificadores. Alternância. PSPACE e Jogos.
- Classe L e NL. Reduções em espaço logarítmico
- Classes de complexidade não uniforme.Circuitos Booleanos e P/poly. Máquinas de Turing com aviso. Limites inferiores.
- Classes de Complexidade Aleatorizadas. Extensão (Ampliação) da noção de eficiência permitindo aos algoritmos o uso de aleatoriedade. Definição de classes de complexidade aleatorizadas, nomeadamente RP, co-RP, BPP e ZPP. Definição de geradores de pseudo-aleatórios.
- Protocolos interactivos. Definição de sistemas de prova interactivos e classes de complexidade IP, AM e MA. Propriedades das classes de complexidade atrás referidas. Reconhecer o papel fundamental da aleatoriedade em protocolos interactivos.
