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 1
Calendar
4-8 maggio 2009
Room
Program
The goal of the course is to provide a formal introduction to complexity and computability theory. The covered topics on computability theory include: universal computational models (single and multi-tape Turing machines, RAM machines, m-recursive functions), Turing decidability and recognisability, reducility, Rice’s theorem, decidability and first order logic, minimum description length. On complexity theory, the introduced topics are: time complexity, P and NP, CoNP, NP-Complete and NP-intermediate, space complexity, probabilistic Turing machines, the polynomial hierarchy. Examples of problems belonging to the introduced computational classes are also given including: decidable/undecidable problems, NP-Complete problems, primality, factorization and graph isomorphism.





 

Courses

PhD Students/Alumni


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