Computational Complexity

Code:

CC4011

Acronym:

CC4011

Level:

400

Keywords
Classification	Keyword
OFICIAL	Computer Science

Instance: 2021/2022 - 2S

Active?	Yes
Web Page:	https://www.dcc.fc.up.pt/~rvr/aulas/AC2122/CC-2122/
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

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. 

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	60,00
Exame	40,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

 Three individual works, where the student needs to achieve a mark of 1/3 (in each of the homewworks), and a final test.

Calculation formula of final grade

The final classification will be the weighted average of the classifications obtaines with the folowing weights: 6/10 for the set of homeworks and 4/10 for the final test.

Special assessment (TE, DA, ...)

Final exam

Classification improvement

Final exam