Complexidade Computacional
Graduação: ICSA41; PPGCC: CCCC
Sumário
Prof. Dr. Leandro M. Zatesko (zatesko(at)utfpr.edu.br)
Disciplina ofertada em conjunto para os cursos de graduação do DAINF da UTFPR-CT (Engenharia de Computação e Sistemas de Informação) e para o Programa de Pós-graduação em Ciência da Computação (PPGCC) da UTFPR-PG.
- Estudantes de outros programas de pós-graduação, como PPGINF/UFPR e PPGCA/UTFPR-CT, também são convidados a participar, devendo se inscrever através deste edital (atenção, pois as inscrições serão exclusivamente até 13 de fevereiro de 2026, podendo ser encerradas antes caso as vagas sejam preenchidas). Via de regra, a solicitação de aproveitamento dos créditos é feita após a conclusão da disciplina. No caso do PPGINF, por exemplo, o regimento prevê que podem ser aproveitados até 4 créditos em disciplinas externas. De qualquer forma, é necessário matricular-se na disciplina do PPGCC como aluno externo através do edital supracitado.
Horário e ensalamento:
- Quartas-feiras, 19:30–21:10, sala CE-208 UTFPR-CT Sede Centro (com o tradicional café levado pelo professor)
- Quintas-feiras, 18:40–20:20, sala CE-203 UTFPR-CT Sede Centro
Google Meet: link divulgado no grupo do Telegram e do Google Classroom para os participantes do curso
- Apenas estudantes de pós-graduação e participantes ouvintes poderão acompanhar a disciplina via Google Meet, mas ainda assim de modo síncrono.
- As aulas não serão (nem podem ser) gravadas.
- Estudantes de Curitiba, ainda que de pós-graduação, são recomendados fortemente a participarem presencialmente. No caso de estudantes de graduação da UTFPR-CT, a participação presencial é obrigatória.
Pré-requisitos:
- Para estudantes de graduação, é obrigatório ter cursado ICSA31 - Teoria da Computação
- Para todos os participantes, é necessário ter conhecimento sobre:
- as classes de complexidade básicas (pelo menos \(\mathsf P\) e \(\mathsf{NP}\));
- o Teorema de Cook–Levin;
- a \(\mathsf{NP}\)-completude dos principais problemas de Karp, como o Problema do Conjunto Independente.
- Estes e outros tópicos podem ser encontrados em Pap93, ArBa09, e nas notas de aula de ICSA31.
Programa
- Apresentação do curso
- As classes P, NP, EXP, NEXP, PSPACE e outras classes de complexidade (Pap93 7.1; ArBa09 2.6 2.7)
- O Método da Alcançabilidade, o Teorema de Savitch, e o Teorema de Immerman–Szelepscényi (Pap93 7.3)
- Teorema de Hierarquia de tempo (Pap93 2.4, 7.2)
- Completude em classes de complexidade (Pap93 16.1; 8.2; 19.1)
- A interseção entre NP e coNP (Pap93 10.1 10.2)
- Máquinas de Turing com oráculos e Teorema de Baker–Gill–Solovay (Pap93 14.3; ArBa09 3.4)
- Teorema de Ladner (ArBa09 3.3)
- Introdução a hierarquia polinomial e Máquinas de Turing alternantes (ArBa09 5.1–5.3)
- Introdução a hierarquia polinomial e Máquinas de Turing alternantes (ArBa09 5.4 5.5; Pap93 Cap. 17)
- A Classe P/poly e Máquinas de Turing aconselhadas (ArBa09 6.1–6.3)
- O Teorema de Karp–Lipton e o Teorema de Meyer (ArBa09 6.4; ArBa09 Theorem 2.18)
- Limitantes inferiores e subclasses de circuitos (ArBa09 6.5)
- Computação Paralela e Complexidade de Circuitos (ArBa09 6.6–6.7)
- Revisão: Teoria de Probabilidade (ArBa09 A.2)
- Máquinas de Turing Probabilísticas e a classe BPP (ArBa09 7.1)
- Máquinas de Turing Probabilísticas e a classe BPP (ArBa09 7.2)
- As classes RP, coRP e ZPP (ArBa09 7.3)
- A classe BPP e suas relações com outras classes (ArBa09 7.4)
- A classe BPP e suas relações com outras classes (ArBa09 7.5)
- A classe PP (Pap93 11. 2)
- Introdução a provas iterativas e a classe IP (ArBa09 8.1)
- A classe AM (ArBa09 8.2)
- A relação entre IP e PSPACE (ArBa09 8.3)
- A relação entre MA, PSPACE, e P/poly (ArBa09 8.4-8.5)
- Provas de conhecimento zero (Vad99 1. 1, 2.5)
- Provas de conhecimento zero (Vad99 3.1)
- Provas verificáveis probabilisticamente (PCP) e algoritmos de aproximação (ArBa09 11. 1)
- Dificuldade de aproximação de problemas NP-difíceis e equivalência entre PCP e dificuldade de aproximação (ArBa09 11. 2)
- Prova da versão fraca do Teorema PCP (ArBa09 11. 5)