Διδακτορικές Σπουδές

Προχωρημένα Θέματα Θεωρητικής Πληροφορικής: Υπολογιστική Πολυπλοκότητα

Περιγραφή

Ορίζονται διάφορες κλάσεις πολυπλοκότητας με βάση τις ακόλουθες παραμέτρους: α) Το υπολογιστικό μοντέλο (προγράμματα σε γλώσσα υψηλής βαθμίδος , μηχανές Turing κτλ.), β) Τον τρόπο υπολογισμού (ντετερμινιστικό, μη ντερμινιστικό, πιθανοτικό κτλ,), γ) Τον περιορισμό των πόρων (πολυωνυμικός χρόνος, λογαριθμικός χώρος, σταθερός αριθμός επεξεργαστών, κτλ.) Μελέτη κλάσεων πολυπλοκότητας και των μεταξύ τους σχέσεων. Προσεγγιστικοί αλγόριθμοι. Παράλληλοι υπολογισμοί. Θέματα: Σχέσεις μεταξύ κλάσεων πολυπλοκότητας. Ιεραρχίες, αναγωγές και πληρότητα, ΝΡ - πλήρη προβλήματα, Co-NP και κλάσεις συναρτήσεων. Το πρόβλημα του ελέγχου αν ένας αριθμός είναι πρώτος, πιθανοτικοί υπολογισμοί και πολυπλοκότητα κυκλωμάτων, κρυπτογραφία, Μονόδρομες συναρτήσεις. Πρωτόκολλα, προσεγγισιμότητα και μη προσεγγισιμότητα, P vs. NP. Ισομορφισμός, μαντεία, μονότονα κυκλώματα, παράλληλοι υπολογισμοί, Μοντέλα. Κλάσεις NC και RNC, λογαριθμικός χώρος. Το πρόβλημα LBA. Εναλλαξιμότητα. Η πολυωνυμική ιεραρχία. Προβλήματα βελτιστοποίησης, μετρητικές κλάσεις. #P και P, Πολυωνυμικός χώρος. Παιχνίδια και διαλογικά πρωτόκολλα, εκθετικός χρόνος κ.α. Προαπαιτούμενα: Μαθήματα σε λογική, θεωρία υπολογισιμότητας και αλγόριθμους και πολυπλοκότητα