Computational Complexity

Code:

CC4011

Acronym:

CC4011

Level:

400

Keywords
Classification	Keyword
OFICIAL	Computer Science

Instance: 2018/2019 - 2S

Active?	Yes
Web Page:	http://www.dcc.fc.up.pt/~nam/web/Teaching/cc2019
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
MI:ERS	1	Plano Oficial desde ano letivo 2014	4	-	6	42	162

Teaching language

Suitable for English-speaking students

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.

(c) Use the concept of interactive proofs in the analysis of optimisation problems.

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

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

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 without final exam

Assessment Components

designation	Weight (%)
Teste	75,00
Trabalho escrito	25,00
Total:	100,00

Amount of time allocated to each course unit

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

Eligibility for exams

The students have to attend the lectures

Calculation formula of final grade

0.75 * assignments  + 0.25 * report

Minimal grade: 9.5