Turing machines.
The universal Turing machine.
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
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.
Working knowledge of a public key cryptographic system.
Prerequisites
Knowledge of induction arguments and proofs by reductio ad absurdum
Turing computability, basic PR functions. Preservation of Turing computability under composition, recursion, minimization. The primitive recursive functions. 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, TRAVELING SALESMAN.Introduction to public key cryptography. Complexity of the euclidean algorithm.