Computational Complexity

Code:

CC4011

Acronym:

CC4011

Level:

400

Keywords
Classification	Keyword
OFICIAL	Computer Science

Instance: 2023/2024 - 2S

Active?	Yes
Web Page:	https://www.dcc.fc.up.pt/~rvr/aulas/AC2324/CC2324/
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	6	Study plan since 2014/2015	1	-	6	42	162
M:ECAD	0	Study plan since 2021/2022	2	-	6	42	162
M:F	2	Official Study Plan	1	-	6	42	162

Teaching language

Portuguese and english

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. 

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 grading.

Evaluation Type

Distributed evaluation with final exam

Assessment Components

designation	Weight (%)
Teste	100,00
Total:	100,00

Amount of time allocated to each course unit

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

Eligibility for exams

 Two tests where the student needs to achieve a mark of 1/3 (in each), and an average of 1/2. 

Calculation formula of final grade

The final classification will be the average of the classifications obtained in the tests.

Special assessment (TE, DA, ...)

Final exam

Classification improvement

Final exam