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

Info

Structure




Logic, Complexity And Computability

 

Prof.
Franco Scarselli
University of Siena - Dipartimento di Ingegneria dell'Informazione e Scienze Matematiche
Course Type
Group 2
Calendar
7,9,11,14,16 febbraio - ore 9:30 -13:00
Room
Program
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.





 

Courses

PhD Students/Alumni


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