University of Siena - Dipartimento di Ingegneria dell'Informazione e Scienze Matematiche
7,9,11,14,16 febbraio - ore 9:30 -13:00
The study of the problems that can be faced by algorithms is a fundamental research area of computer science. While computability theory studies which problems can be given algorithmic solutions, complexity theory is focused on the amount of memory and the time resources required by the computation. In this course, fundamental results from this area will be reviewed and some advanced arguments will be sketched. The topics about computability will include Turing machine and other universal models, undecidable problems, Rice theorem, minimum description length and undecidability of first order logic. The presentation on complexity will deal with the classes P, NP, coP, coNP and their relationships, polynomial time reduction, Cook-Levin Theorem, isomorphism, sparse languages, spatial complexity, probabilistic algorithms and quantum computing.