Επαγωγικές αποδείξεις και αναδροµικοί ορισµοί. Εισαγωγή µοντέλων υπολογισµού. Πρωτογενείς αναδροµικές συναρτήσεις και σχέσεις. Μερικές αναδροµικές συναρτήσεις και ελαχιστοποίηση. Μηχανική υπολογισιµότητα. Μηχανές Turing και Turing υπολογίσιµες συναρτήσεις. Θέση Church-Turing. Τα βασικά θεωρήµατα: Κανονικού τύπου, απαρίθµησης και παραµέτρων (s-m-n). Αναδροµικά απαριθµήσιµα σύνολα και ανεπίλυτα προβλήµατα. Ορισιµότητα και αριθµητική ιεραρχία. Turing αναγωγισιµότητα και βαθµοί αναποκρισιµότητας. Υπολογιστική πολυπλοκότητα. Αιτιοκρατικές και µη-αιτιοκρατικές µηχανές Turing. Οι κλάσεις P και NP. Πολυωνυµικοί µετασχηµατισµοί και NP-πληρότητα. Το θεώρηµα του Cook. NP-πλήρη προβλήµατα και αναγωγές.
Χειμ. Εξάμηνο 2012 - 2013.
Πρόγραμμα: Τρίτη 12.00-15.00, Αίθ. 1.