Introduce the complexity classes related to the most recent computing paradigms. At the end of the course the students will be able to compare the computational power of the new computing paradigms with the computational power of the more established ones.
teacher profile teaching materials
Complexity of Randomized Computing.
Complexity of Quantum Computing.
Programme
Complexity paradigms for Big Data and Cloud Computing: the Pspace class, Pspace-completeness, Savitch's theorem, the L and NL classes, NL-completeness.Complexity of Randomized Computing.
Complexity of Quantum Computing.
Core Documentation
Slide fornite dal docente.Type of delivery of the course
Traditional lectures and exercises.Type of evaluation
On-going assessment: alternatively to the exam you can use the on-going assessment (intermediate tests). The ongoing evaluation is not mutually exclusive to the traditional one, however, the student who presents himself for the exam in a regular appeal implicitly refuses the mark of the ongoing evaluation. The result of the ongoing assessment, if accepted by the student, will be recorded only in the first exam session. 1 intermediate test is foreseen.