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

Λεπτομερής Πολυπλοκότητα

---

Περιγραφή

Λεπτομερής Πολυπλοκότητα

Η παραδοσιακή θεωρία Υπολογιστικής Πολυπλοκότητας διαχωρίζει τα υπολογιστικά προβλήματα σε αυτά που μπορούν να επιλυθούν σε πολυωνυμικό χρόνο και σε αυτά που είναι NP-δύσκολα, και δεν παρέχει εργαλεία για πιο λεπτομερείς κατηγοριοποιήσεις. Για παράδειγμα, η χρήση της εικασίας ότι οι κλάσεις P και NP διαφέρουν δεν αρκεί για να ρίξει φως σε ερωτήματα του τύπου "μπορεί το πρόβλημα των Συντομότερων Μονοπατιών να λυθεί σε χρόνο O(n^{2.99});" ή "μπορεί το πρόβλημα του Περιοδεύοντος πωλητή να λυθεί σε χρόνο O(n^{log n});", παρόλο που η γενική πεποίθηση των ειδικών είναι ότι η απάντηση είναι αρνητική. Η θεωρία της Λεπτομερούς Πολυπλοκότητας ξεκινάει από πιο ισχυρές εικασίες για τη δυσκολία ενός μικρού πλήθους προβλημάτων (όπως ότι το k-SAT δε μπορεί να λυθεί σε υποεκθετικό χρόνο), και μέσω κατάλληλων αναγωγών συμπληρώνει τα υπολογιστικά κενά στα οποία δε μπορεί να φτάσει η παραδοσιακή προσέγγιση. Ενδεικτικά, στα πλαίσια της θεωρίας αυτής αποδείχθηκε ότι δεν μπορεί να υπάρχει αυστήρα υποτετραγωνικός αλγόριθμος για το πρόβλημα της μέγιστης κοινής υπακολουθίας, εκτός εάν το k-SAT λύνεται σε χρόνο Ο(2^{(1-δ)n}) για κάποια σταθερά δ. Στο μάθημα αυτό θα δούμε τις πρωταρχικές εικασίες που αποτελούν τη βάση του νεοσύστατου αυτού κλάδου, καθώς και (εντυπωσιακά) παραδείγματα αναγωγών τα οποία υποδεικνύουν ότι η ύπαρξη σημαντικά γρηγορότερων αλγόριθμων για ορισμένα προβλήματα θα ισοδυναμούσε με τεράστια αλγοριθμική πρόοδο σε προβλήματα στα οποία εδώ και δεκαετίες η αλγοριθμική μας κατανόηση έχει ουσιαστικά καθηλωθεί στις τετριμμένες προσεγγίσεις.

Περιεχόμενο: (Ισχυρή) Υπόθεση Εκθετικού Χρόνου και Ορθογώνια Διανύσματα. Πολυωνυμική Μέθοδος. Αραιοποίηση. Δυσκολία Μέγιστου Ανεξάρτητου συνόλου και Μέγιστης Κοινής Υπακολουθίας. (Min,+)-συνέλιξη και δυσκολία υποτετραγωνικών FPTAS για Άθροισμα Υποσυνόλου και Πρόβλημα Σακιδίου. Πρόβλημα συντομότερων μονοπατιών. Πολλαπλασιασμός πινάκων Boole. Δυσκολία προβλημάτων υπολογιστικής γεωμετρίας ως προς το 3SUM. Λογαριθμική βελτίωση για το 3SUM και δέντρα αποφάσεων. Λεπτομερής πολυπλοκότητα παραμετρικής και προσεγγιστικής επίλυσης.

Fine-Grained Complexity

Τraditional Computational Complexity theory classifies computational problems either to those that can be solved in polynomial time or to those that are NP-hard and does not offer tools for finer classifications. For example, the mere use of the conjecture that classes P and NP differ has not managed to shed light to questions such as "can Shortest Paths problem be solved faster than O(n^{2.99})?" or "can the Traveling Salesman Problem be solved in time O(n^{log n})?" although it is widely believed by experts that the answer is negative. Fine-Grained Complexity Theory starts from strong conjectures about the hardness of a small number of problems (for example, that k-SAT cannot be solved in subexponential time), and fills the gaps that traditional theory fails to handle through appropriate reductions. Indicatively, it was proven in the context of this theory that if there exists a strictly subquadratic algorithm for the problem of Longest Common Subsequence, then k-SAT can be solved in time O(2^{(1-δ)n}) for some constant δ. In this course we will study the primary conjectures that constitute the basis of this recent field, as well as (impressive) examples of reductions which suggest that the existence of considerably faster algorithms for certain problems would imply huge algorithmic progress for problems which for decades have evaded our algorithmic understanding beyond essentially trivial approaches.

Contents: (Strong) Exponential Time Hypothesis and Orthogonal Vectors. Polynomial Method. Sparcification. Hardnes of Maximum Independent Set and Longest Common Subsequence. (Min,+) convolution and hardness of subquadratic FPTAS for Subset Sum and Knapsack. All-Pairs Shortest Paths. Boolean Matrix Multiplication. 3SUM-hardness of geometric problems. Decision trees and logarithmic improvement for 3SUM. Fine-grained complexity of parameterized and approximate solving.