Καλημέρα,

ο φοιτητής του ΑΛΜΑ Σταύρος Ταξιάρχης Ποτσάκης θα παρουσιάσει τη διπλωματική του εργασία με θέμα:

"Η Δυναμική Πολυπλοκότητα του προβλήματος 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.

Τα στοιχεία του meeting είναι τα παρακάτω:

Meeting Information
Meeting link:
https://centralntua.webex.com/centralntua/j.php?MTID=m57150f6a08a88807cf115e9b55fdfe08

Meeting number:
121 117 4347
Password:
8HFp72xpp7y