Disciplina Discipline MAC5722
Complexidade Computacional

Computational Complexity

Área de Concentração: 45134

Concentration area: 45134

Criação: 02/06/2023

Creation: 02/06/2023

Ativação: 22/06/2023

Activation: 22/06/2023

Nr. de Créditos: 8

Credits: 8

Carga Horária:

Workload:

Teórica

(por semana)

Theory

(weekly)

Prática

(por semana)

Practice

(weekly)

Estudos

(por semana)

Study

(weekly)

Duração Duration Total Total
4 2 4 12 semanas 12 weeks 120 horas 120 hours

Docentes Responsáveis:

Professors:

Yoshiharu Kohayakawa

Fábio Happ Botler

Guilherme Oliveira Mota

Objetivos:

Desenvolver o estudo de complexidade computacional, supondo já conhecidos os elementos básicos da teoria.

Objectives:

Develop the study of computational complexity, assuming the basic elements of the theory are known.

Justificativa:

Esta é uma disciplina voltada especificamente à teoria da complexidade computacional, adequada para alunos interessados em teoria da computação.

Rationale:

This course focuses on computational complexity theory, for students interested in the theory of computation.

Conteúdo:

O Teorema de Cook--Levin. Complexidade de espaço. Teoremas de hierarquia e diagonalização. A hierarquia polinomial. Algoritmos probabilísticos e de aproximação. Provas interativas. O Teorema PCP. Tópicos adicionais: Complexidade de circuitos, Criptografia ou Computação quântica.

Content:

The Cook--Levin Theorem. Space complexity. Hierarchy theorems and diagonalization. The polynomial hierarchy. Probabilistic and approximation algorithms. Interactive proofs. The PCP Theorem. Further topics: Circuit complexity, Cryptography or Quantum computing.

Forma de Avaliação:

A avaliação será realizada através de seminários, projetos e provas. A nota final será calculada pela média aritmética M das médias obtidas pelo aluno em cada instrumento de avaliação. Nas duas primeiras semanas de aula o docente fixará as datas e o número de provas, projetos e seminários, assim como o critério de atribuição do conceito final.

Type of Assessment:

The evaluation will be carried out through seminars, projects and tests. The final grade will be calculated by the arithmetic mean M of the means obtained by the student in each assessment instrument. In the first two weeks of class, the teacher will set the dates and number of tests, projects and seminars, as well as the criteria for attributing the final letter grade.

Bibliografia:

1. S. Arora e B. Barak, Computational complexity. A modern approach. Cambridge University Press, Cambridge, 2009. xxiv + 579pp. ISBN: 978-0-521-42426-4 2. M. Sipser, Introduction to the Theory of Computation. Cengage Learning, Boston, MA. 3rd edition, 2013. xxii + 458pp. 3. C. H. Papadimitriou, Computational complexity. Addison-Wesley Publishing Company, Reading, MA, 1994. xvi + 523pp. ISBN: 0-201-53082-1 4. H. R. Lewis, C. H. Papadimitriou, Elementos de Teoria da Computação, 2nd ed., Bookman, 2000.

Bibliography:

1. S. Arora e B. Barak, Computational complexity. A modern approach. Cambridge University Press, Cambridge, 2009. xxiv + 579pp. ISBN: 978-0-521-42426-4 2. M. Sipser, Introduction to the Theory of Computation. Cengage Learning, Boston, MA. 3rd edition, 2013. xxii + 458pp. 3. C. H. Papadimitriou, Computational complexity. Addison-Wesley Publishing Company, Reading, MA, 1994. xvi + 523pp. ISBN: 0-201-53082-1 4. H. R. Lewis, C. H. Papadimitriou, Elementos de Teoria da Computação, 2nd ed., Bookman, 2000.

Idiomas ministrados:

Português

Languages taught:

Portuguese

Tipo de oferecimento da disciplina:

Presencial

Class type:

Presencial