Ο φοιτητής του προγράμματος Σταύρος Ταξιάρχης Ποτσάκης θα παρουσιάσει τη διπλωματική του εργασία με θέμα:
Η Δυναμική Πολυπλοκότητα του προβλήματος Reachability και Σχετικών Προβλημάτων
την Τετάρτη 9 Ιουνίου 2021 και ώρα 12:00, μέσω τηλεμετάδοσης (Webex).
Σύνοψη Διπλωματικής:
Το reachability query είναι σημαντικού ενδιαφέροντος για την έρευνα της εκφραστικής δύναμης της DynFO, αφού είναι ένα από τα πιο απλά ερωτήματα τα οποία δεν μπορούν να περιγραφούν στατικά σε λογική πρώτης τάξης, αλλά απαιτούν αναδρομή. Θα εισάγουμε τη θεωρία της Δυναμικής Πολυπλοκότητας χρησιμοποιώντας έννοιες από την περιγραφική πολυπλοκότητα. Θα μελετήσουμε την κλάση DynFO δείχνοντας προβλήματα να ανήκουν σε αυτήν αλλά και τη σχέση DynFO με άλλες κλάσεις πολυπλοκότητας όπως οι P, P-complete, L-complete, NL-complete και DynAC^0. Επίσης ορίζουμε τις "bounded-expansion" πρώτης τάξης αναγωγές οι οποίες τιμούν τις δυναμικές κλάσεις πολυπλοκότητας. Στη συνέχεια δίνουμε μια λεπτομερή απόδειξη του προβλήματος του Reachability να ανήκει στη DynFO χρησιμοποιώντας προβλήματα της υπολογιστικής γραμμικής άλγεβρας. Επιπλέον, χρησιμοποιώντας το παραπάνω αποτέλεσμα και τις τεχνικές τις αποδειξής του, αποδεικνύουμε ότι 2-SAT ανήκει στη DynFO και PerfectMatching and Maxmatching ανήκουν στη μη ομοιόμορφη DynFO.
Η Επιτροπή,
Αρχοντία Γιαννοπούλου,
Τμήμα Πληροφορικής και Τηλεπικοινωνιών, ΕΚΠΑ
Στάθης Ζάχος (Επιβλέπων),
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, ΕΜΠ
Δημήτριος Θηλυκός,
Τμήμα Μαθηματικών, ΕΚΠΑ