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