Coordinator: Prof. Antonio Vicino
Home |  DIISM |   | Login Privacy e Cookie policy



Logic, Complexity And Computability


Franco Scarselli
University of Siena - Dipartimento di Ingegneria dell'Informazione e Scienze Matematiche
Course Type
Type B
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.



PhD Students/Alumni

Dip. Ingegneria dell'Informazione e Scienze Matematiche - Via Roma, 56 53100 SIENA - Italy