Computational Complexity

Code:

CC4011

Acronym:

CC4011

Level:

400

Keywords
Classification	Keyword
OFICIAL	Computer Science

Instance: 2020/2021 - 2S

Active?	Yes
Responsible unit:	Department of Computer Science
Course/CS Responsible:	Master in Computer Science

Cycles of Study/Courses

Acronym	No. of Students	Study Plan	Curricular Years	Credits UCN	Credits ECTS	Contact hours	Total Time
M:CC	11	Study plan since 2014/2015	1	-	6	42	162
MI:ERS	6	Plano Oficial desde ano letivo 2014	4	-	6	42	162

Teaching language

Portuguese

Objectives

We will study some techniques that prove or suggest that there are no known eficient method to solve some important problems in computer science. We will study several complexity classes and their relationship, namely: P, NP, co-NP, PH, RP, BPP, IP. Special emphasis will be given to the role of randomness in the performance of several algorithms.

Learning outcomes and competences

Upon successful completion of this course, students will be able to:

(a) Distinguish between complexity classes.

(b) Classify decision problems into appropriate complexity classes, including P, NP, PSPACE and complexity classes based on randomised machine models and use this information effectively.

Working method

Presencial

Program

1) Motivation and background
2) Complexity classes $P$ and $NP$
3) Polynomial time hierarchy
4) Class PSPACE and Alternation
4) Non-uniform Models. Boolean Circuits, machines with advice. Class P/poly
5)Randomized complexity classes: RP, BPP and ZPP
6) Interactive protocols, classes IP, AM e MA

Mandatory literature

Sanjeev Arora and Boaz Barak; Complexity Theory: A Modern Approach
Oded Goldreich; Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008. ISBN: 978-0-521-88473-0

Complementary Bibliography

Michael Garey and David Johnson; Computers and intractability: A guide to NP-Completeness, W. H. Freeman, 1979. ISBN: 0716710455
C. Papadimitriou; Computational complexity, Addison Wesley Longman, 1994. ISBN: 0201530821
D.Z. Du and K.I. Ko; Theory of Computational Complexity, John Wiley and Sons, 2000. ISBN: 978-0-471-34506-0

Teaching methods and learning activities

Lectures  with practical assignments.
Distributed evaluation with  practical assignments and a final report and presentation.

Evaluation Type

Distributed evaluation with final exam

Assessment Components

designation	Weight (%)
Teste	70,00
Exame	30,00
Total:	100,00

Amount of time allocated to each course unit

designation	Time (hours)
Frequência das aulas	45,00
Estudo autónomo	117,00
Total:	162,00

Eligibility for exams

 Two practical tests, it is mandatory to have an average of 8 out of 20 in the tests.

Calculation formula of final grade

Distributed evaluation with final exam: students are assessed by their performance with  two practical assignments.  It is mandatory to have an average of 8 out of 20 in the tests to be able to do the final exam. If the student has an average bigger than 10 out of 20 in the tests he will allowed to keep the grade without the final exam, otherwise the final classification will be the average of the final exam with the average of the tests.