Person in charge:  () 
Others:  () 
Credits  Dept.  Type  Requirements 

7.5 (6.0 ECTS)  CS 

ADA
 Prerequisite for DIE TC  Prerequisite for DIE 
Person in charge:  () 
Others:  () 
In the study of complexity theory, students look at computational problems by regarding them as mathematical objects that can be analysed, interrelated and classified based on the computational resources required to solve them. Students analyse the limits of computation in classes focused on complexity, problems and algorithms. The aim of the subject is to give students an indepth look into the inherent difficulty of problems and to strengthen their ability to classify problems in the light of different criteria based on the consideration of different computational resources.
Estimated time (hours):
T  P  L  Alt  Ext. L  Stu  A. time 
Theory  Problems  Laboratory  Other activities  External Laboratory  Study  Additional time 

T  P  L  Alt  Ext. L  Stu  A. time  Total  

3,0  2,0  0  0  0  5,0  0  10,0  
Natural problems:
Satisfiability of Boolean formulae, Subgraphs, Partitions, Paths, Resource allocation. 

T  P  L  Alt  Ext. L  Stu  A. time  Total  

6,0  4,0  0  0  0  10,0  0  20,0  
Natural problems:
Satisfiability of Boolean formulae, Subgraphs, Partitions, Paths, Resource allocation. 

T  P  L  Alt  Ext. L  Stu  A. time  Total  

10,0  5,0  0  0  0  15,0  0  30,0  
Natural problems.
Turing reducibility. The Polynomial Time Hierarchy. Approximability. Polynomial hierarchy. 

T  P  L  Alt  Ext. L  Stu  A. time  Total  

6,0  4,0  0  0  0  10,0  0  20,0  
The complexity of games such as Go, Chess, and Chequers. The permanent. 

T  P  L  Alt  Ext. L  Stu  A. time  Total  

6,0  4,0  0  0  0  10,0  0  20,0  
Classes of problems. Complete problems. 

T  P  L  Alt  Ext. L  Stu  A. time  Total  

6,0  4,0  0  0  0  10,0  0  20,0  
Protocol to the Permanent.
Protocol to QBF: IP?PSPACE. Applications: Zero Information in Criptography. Graph isomorphisms and nocompleteness. Parallel computing. P versus NC. NC and AC classes. Logarithmic space. 

T  P  L  Alt  Ext. L  Stu  A. time  Total  

6,0  4,0  0  0  0  10,0  0  20,0  
Natural problems: Grpha accessibility.
Logarithmic Space: L and NL. Parallel Computation Models: PRAM and Circuits. NC and AC. 
Total per kind  T  P  L  Alt  Ext. L  Stu  A. time  Total 
46,0  29,0  0  0  0  75,0  0  150,0  
Avaluation additional hours  3,0  
Total work hours for student  153,0 
()
Exercises:
Some of the problems will involve solving a short list of problems allocated to each student (or small work group) at the end of each course theme. Students will be given the opportunity to raise questions in class.
Nevertheless, the assignments are to be completed by individual students or groups (as the case may be) during private study.
In general, the solution to these problems will require both the concepts learnt earlier and recourse to the relevant bibliography.
The work will be submitted a week or two after the assignments were set.
Those solutions throwing light on a current theme or which extend students knowledge will be presented in class.
Exam:
A final exam will be set to assess the extent to which students have acquired the fundamental principles introduced during the course.
The grade awarded for the course as a whole is based on the grade for problems (P) and the final exam grade (E) as follows:
Final Grade= MAX {(P+E)/2,E}
()