Complexity (COM)

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 in-depth 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.

Knowledges

Abilities

Competences

(-)

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}

• Papadimitriou, C. Computational complexity, Addison Wesley, 1994.
• Balcázar J. L., Díaz J., Gabarró J. Structural Complexity I, Springer-Verlag, 1995.
• Sipser, M. Introduction to the theory of computation, 2nd Edition, PWS publishing Company, 2005.

(-)