Turing machines.
The universal Turing machine.
Basic notions of computability.
Basic logic notions for CNF formulas.
The class NP, NP-complete problems.
Introduction to public key cryptography.
Complexity of the euclidean algorithm.
D.Mundici, "Dalla macchina di Turing a P/NP", McGraw-Hill, 2013
Other suggested textbook:
Garey, Johnson, "Computers and intractability", 1979
Learning Objectives
Analysis and synthesis of Turing machines.
Working knowledge of the fundamental theorems on computability and complexity theory.
Ability to assess the computational complexity of problems.
Prerequisites
Knowledge of induction arguments and proofs by reductio ad absurdum
Teaching Methods
Lecturing, Tutoring, Exercises
Further information
Attendance is recommended.
Type of Assessment
Oral examination
Course program
Turing computability, basic PR functions. Preservation of Turing computability under composition, recursion, minimization. The primitive recursive functions. Recursive functions and sets and some of their properties. Church-Turing thesis (particular case: recursive = Turing computable). Turing's theorem on the universal Turing machine.Turing’s theorem on the undecidability of the halting problem. Syntax and semantics of CNF formulas. Distinction between intractable and tractable problems. The class NP. NP-complete problems. The P/NP problem. NP-completeness of
CNFSAT, KNAPSACK, COLORABILITY, CLIQUE, INDEPENDENT SET, VERTEX COVER, TRAVELING SALESMAN, 3 DIMENSIONAL MATCHING, PARTITION, HAMILTON CIRCUIT.