| Περίληψη: | Η παρούσα διπλωματική εργασία πραγματεύεται ορισμένα σημαντικά αποτελέσματα των δυνατοτήτων ενός απλού υπολογιστικού μοντέλου, των λογικών κυκλωμάτων, τα οποία παρουσιάστηκαν στη βιβλιογραφία τα τελευταία
τριάντα χρόνια.
Παρόμοια με την ευρύτερα χρησιμοποιούμενη μηχανή Turing, τα λογικά
κυκλώματα παρουσιάζουν τα δικά τους χαρακτηριστικά, τα οποία είναι το
μέγεθος και το βάθος. Όσον αφορά τα αποτελέσματα σχετικά με την υπολογιστική πολυπλοκότητα που εξάγονται με βάση το συγκεκριμένο μοντέλο, αυτά
συμβαδίζουν σε γενικές γραμμές με την παραδοσιακή υπολογιστική πολυπλοκότητα. Συνεπώς, στρεφόμαστε προς την ταξινόμηση των διάφορων προβλη-
μάτων σε νέες και πιθανόν ενδιαφέρουσες κλάσεις, καθώς και στην εξαγωγή
κάτω φραγμάτων για συγκεκριμένα προβλήματα. Οι εφαρμοζόμενες τεχνικές
είναι πρωτότυπες και μη-τετριμμένες και σε πολλές περιπτώσεις κατά το παρελθόν είχαν δικαιολογημένα δημιουργήσει προσδοκίες για σημαντική πρόοδο στο συγκεκριμένο πεδίο.
Στα πλαίσια της συγκεκριμένης εργασίας, ορίζεται πρωτίστως το μοντέλο
και οι διάφορες παραλλαγές του, και σε επόμενο στάδιο εξετάζονται ορισμένες από τις τεχνικές που χρησιμοποιούνται στο παρόν επιστημονικό πεδίο. Στη
συνέχεια, περιγράφουμε λεπτομερώς δύο από τα κυριότερα αποτελέσματα στην
περιοχή, αυτό του κάτω φράγματος στη συνάρτηση Ισοτιμίας με τη χρήση του λεγόμενου Λήμματος Εναλλαγής του Håstad καθώς και το σημαντικό αποτέλεσμα του Razborov της εύρεσης ενός κάτω φράγματος για το πρόβλημα της
ΚΛΙΚΑΣ. Το αποτέλεσμα αυτό δημιούργησε μεγάλο ενθουσιασμό κατά το παρελθόν καθώς θεωρήθηκε ως ένα μεγάλο βήμα για την επίλυση του διάσημου
προβλήματος P vs NP.
|
|---|
