Το 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.
Όνομα
Σταύρος Ταξιάρχης Ποτσάκης
Ημερομηνία παρουσίασης
09-06-2021
Τριμελής επιτροπή
Αρχοντία Γιαννοπούλου
Στάθης Ζάχος (Επιβλέπων)
Δημήτριος Θηλυκός
Σύνοψη