Complexity

Code:

CC441

Acronym:

CC441

Keywords
Classification	Keyword
OFICIAL	Computer Science

Instance: 2010/2011 - 2S

Active?	Yes
Responsible unit:	Department of Computer Science
Course/CS Responsible:	Master's Degree in Network and Information Systems Engineering

Cycles of Study/Courses

Acronym	No. of Students	Study Plan	Curricular Years	Credits UCN	Credits ECTS	Contact hours	Total Time
M:CC	4	PE do Mestrado em Ciência de Computadores	1	-	7,5	67	202,5
M:ENM	2	PE do Mestrado em Engenharia Matemática	1	-	7,5	67	202,5
			2
MI:ERS	1	Plano de Estudos a partir de 2007	4	-	7,5	67	202,5
M:MAO	1	PE Mestrado em MAOPI	1	-	7,5	67	202,5

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.

Program

1) Motivation and background
2) Complexity classes $P$ and $NP$
3) Polynomial time hierarchy
4) Randomized complexity classes
5) Interactive protocols, classes $IP$, $AM$ e $MA$
6) Zero knowledge protocols

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

Evaluation Type

Distributed evaluation without final exam

Assessment Components

Description	Type	Time (hours)	Weight (%)	End date
Attendance (estimated)	Participação presencial	67,50
1st exam	Exame	2,00		2011-04-05
2nd exam	Exame	2,00		2011-05-31
	Total:	-	0,00

Calculation formula of final grade

1/2 * 1st exam + 1/2 * 2nd exam