Ενοποίηση Σχετικιστικών Και Φυσικών Αποδείξεων Για Την Εύρεση Νέων Κάτω Φραγμάτων

Abstract

Στην παρούσα Διπλωματική Εργασία μελετάμε τη σύνδεση των ανομοιόμορφων μοντέλων υπολογισμού με τις παραδοσιακές υπολογιστικές δυνατότητες των μηχανών Turing. Συγκεκριμένα τα πρώτα είναι στενά συνδεδεμένα με τις οικογένειες λογικών κυκλωμάτων και αποδεικνύεται ότι, ακριβώς χάρη στην ανομοιομορφία τους, αποτελούν ένα παντοδύναμο υπολογιστικό μοντέλο, καθιστώντας τα ισχυρότερα από όλες τις γνωστές υπολογιστικές μεθόδους αλλά με το προφανές μειονέκτημα ότι δεν μπορούν να υλοποιηθούν ρεαλιστικά. Εν τούτοις, αποτελούν ένα πολύ αποδοτικό εργαλείο ως μέτρο συμπύκνωσης των υπολογιστικών βημάτων που απαιτεί ο υπολογισμός μιας συνάρτησης και φαίνεται να έχουν αμέτρητες εφαρμογές και συνδέσεις με τις ομοιόμορφες υπολογιστικές κλάσεις. Αποκορύφωμα αυτών, είναι μέχρις στιγμής η στενή σύνδεση της εικασίας ανυπαρξίας χαμηλών κυκλωματικών κλάσεων για υψηλές υπολογιστικές κλάσεις με τη δυνατότητα αποδοτικά ομοιόμορφης παραγωγής ψευδοτυχαιότητας (μία από τις κρισιμότερες παραμέτρους στη σύγχρονη Κρυπτογραφία). Από την άλλη το πεδίο των Κυκλωμάτων φάνηκε να αποτελεί το πιο εύφορο πεδίο για την εύρεση φραγμάτων στις υπολογιστικές δυνατότητες ομοιόμορφων κλάσεων περιορισμένων πόρων (χρόνου, χώρου κ.λπ.), ειδικότερα μετά την απόδειξη της αδυναμίας των απλών επιχειρημάτων αυτοαναφοράς να λύσουν μεγάλα ανοιχτά ερωτήματα της Θεωρίας Πολυπλοκότητας (όπως αν $P=NP$, $P=BPP$ κ.ο.κ.). Εν τούτοις, το ομώνυμο άρθρο περί των Φυσικών Αποδείξεων για αρκετό καιρό είχε απογοητεύσει την επιστημονική κοινότητα όσον αφορά την πιθανότητα ύπαρξης μιας απλής απόδειξης που να χαρακτηρίζει με τεχνικά επιχειρήματα τις συναρτήσεις που επιδέχονται κυκλώματα πολυωνυμικού μεγέθους. Τα εμπόδια αυτά φαίνεται πως έρχεται να άρει μια σχετικά πρόσφατη μέθοδος, η οποία προτάθηκε κατά κύριο λόγο από τον Ryan Williams και η οποία χρησιμοποιεί την παραγωγή μη τετριμμένων αλγορίθμων για κυκλώματα (εκμεταλλεύοντας τεχνικές ιδιότητες συγκεκριμένων κυκλωματικών κλάσεων) και η οποία στη συνέχεια κατασκευάζει μια κυκλωματική δομή που να υπολογίζει σχετικούς αλγόριθμους σε χρόνο που αντιβαίνει παραδοσιακά επιχειρήματα διαγωνιοποίησης. Η μέθοδος αυτή είναι αφενός ελπιδοφόρα επειδή, συνδυάζοντας συντακτικές και σημασιολογικές τεχνικές, φαίνεται η κάθε πλευρά να είναι ικανή να καλύψει τις αδυναμίες που είχε η άλλη (όταν χρησιμοποιούνταν αυτοτελώς), αλλά και αφετέρου επειδή έχει ήδη δείξει τις δυνατότητες της μέσω του πρόσφατου αποτελέσματος (επίσης από τον R.W.) ότι $NEXP \nsubseteq ACC^0$ συνοδευόμενου από μια πληθώρα θεωρημάτων ικανών να παράξουν μια εν δυνάμει μεγάλη ποικιλία νέων κάτω φραγμάτων.