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