Κυκλωματική πολυπλοκότητα
Η παρούσα διπλωματική εργασία πραγματεύεται ορισμένα σημαντικά αποτελέσματα των δυνατοτήτων ενός απλού υπολογιστικού μοντέλου, των λογικών κυκλωμάτων, τα οποία παρουσιάστηκαν στη βιβλιογραφία τα τελευταία τριάντα χρόνια. Παρόμοια με την ευρύτερα χρησιμοποιούμενη μηχανή Turing, τα λογικά κυκλώματα...
| Κύριος συγγραφέας: | |
|---|---|
| Άλλοι συγγραφείς: | |
| Μορφή: | Thesis |
| Γλώσσα: | Greek |
| Έκδοση: |
2016
|
| Θέματα: | |
| Διαθέσιμο Online: | http://hdl.handle.net/10889/9487 |
| id |
nemertes-10889-9487 |
|---|---|
| record_format |
dspace |
| spelling |
nemertes-10889-94872022-09-05T05:37:41Z Κυκλωματική πολυπλοκότητα Παναγοπούλου, Αγγελική Παναγιώτα Καββαδίας, Δημήτριος Μακρή, Ευφροσύνη Καραζέρης, Παναγής Panagopoulou, Aggeliki Panagiota Λογικά κυκλώματα Κυκλωματική πολυπλοκότητα Μονότονα κυκλώματα Logical circuits Circuit complexity Monotone circuits 511.3 Η παρούσα διπλωματική εργασία πραγματεύεται ορισμένα σημαντικά αποτελέσματα των δυνατοτήτων ενός απλού υπολογιστικού μοντέλου, των λογικών κυκλωμάτων, τα οποία παρουσιάστηκαν στη βιβλιογραφία τα τελευταία τριάντα χρόνια. Παρόμοια με την ευρύτερα χρησιμοποιούμενη μηχανή Turing, τα λογικά κυκλώματα παρουσιάζουν τα δικά τους χαρακτηριστικά, τα οποία είναι το μέγεθος και το βάθος. Όσον αφορά τα αποτελέσματα σχετικά με την υπολογιστική πολυπλοκότητα που εξάγονται με βάση το συγκεκριμένο μοντέλο, αυτά συμβαδίζουν σε γενικές γραμμές με την παραδοσιακή υπολογιστική πολυπλοκότητα. Συνεπώς, στρεφόμαστε προς την ταξινόμηση των διάφορων προβλη- μάτων σε νέες και πιθανόν ενδιαφέρουσες κλάσεις, καθώς και στην εξαγωγή κάτω φραγμάτων για συγκεκριμένα προβλήματα. Οι εφαρμοζόμενες τεχνικές είναι πρωτότυπες και μη-τετριμμένες και σε πολλές περιπτώσεις κατά το παρελθόν είχαν δικαιολογημένα δημιουργήσει προσδοκίες για σημαντική πρόοδο στο συγκεκριμένο πεδίο. Στα πλαίσια της συγκεκριμένης εργασίας, ορίζεται πρωτίστως το μοντέλο και οι διάφορες παραλλαγές του, και σε επόμενο στάδιο εξετάζονται ορισμένες από τις τεχνικές που χρησιμοποιούνται στο παρόν επιστημονικό πεδίο. Στη συνέχεια, περιγράφουμε λεπτομερώς δύο από τα κυριότερα αποτελέσματα στην περιοχή, αυτό του κάτω φράγματος στη συνάρτηση Ισοτιμίας με τη χρήση του λεγόμενου Λήμματος Εναλλαγής του Håstad καθώς και το σημαντικό αποτέλεσμα του Razborov της εύρεσης ενός κάτω φράγματος για το πρόβλημα της ΚΛΙΚΑΣ. Το αποτέλεσμα αυτό δημιούργησε μεγάλο ενθουσιασμό κατά το παρελθόν καθώς θεωρήθηκε ως ένα μεγάλο βήμα για την επίλυση του διάσημου προβλήματος P vs NP. This thesis deals with some important results on the computational abilities of a simple computational model called the logical circuit, that have appeared in the literature the last thirty years. Analogously to the more widely used Turing machine, the logical circuit has its own resources of interest, namely its size and depth. Computational complexity results based on this model move along similar lines with traditional computational complexity, that is, first toward classifying various problems in new and hopefully interesting classes and also in obtaining lower bounds for individual problems. The techniques employed are novel and non-trivial and in several occasions in the past have created justified expectations of making a real breakthrough in the field. In the thesis we first define the model and its variants and then review some of the techniques used in the field. We next describe in detail two of the main results in the field, the lower bound on the Parity function using Hastad's Switching Lemma and the celebrated result by Razborov on a lower bound for the famous CLIQUE problem. This result has created much excitement in the past as it was considered as a major step toward resolving the famous P vs NP problem. 2016-07-25T07:35:30Z 2016-07-25T07:35:30Z 2015-07 Thesis http://hdl.handle.net/10889/9487 gr 12 application/pdf |
| institution |
UPatras |
| collection |
Nemertes |
| language |
Greek |
| topic |
Λογικά κυκλώματα Κυκλωματική πολυπλοκότητα Μονότονα κυκλώματα Logical circuits Circuit complexity Monotone circuits 511.3 |
| spellingShingle |
Λογικά κυκλώματα Κυκλωματική πολυπλοκότητα Μονότονα κυκλώματα Logical circuits Circuit complexity Monotone circuits 511.3 Παναγοπούλου, Αγγελική Παναγιώτα Κυκλωματική πολυπλοκότητα |
| description |
Η παρούσα διπλωματική εργασία πραγματεύεται ορισμένα σημαντικά αποτελέσματα των δυνατοτήτων ενός απλού υπολογιστικού μοντέλου, των λογικών κυκλωμάτων, τα οποία παρουσιάστηκαν στη βιβλιογραφία τα τελευταία
τριάντα χρόνια.
Παρόμοια με την ευρύτερα χρησιμοποιούμενη μηχανή Turing, τα λογικά
κυκλώματα παρουσιάζουν τα δικά τους χαρακτηριστικά, τα οποία είναι το
μέγεθος και το βάθος. Όσον αφορά τα αποτελέσματα σχετικά με την υπολογιστική πολυπλοκότητα που εξάγονται με βάση το συγκεκριμένο μοντέλο, αυτά
συμβαδίζουν σε γενικές γραμμές με την παραδοσιακή υπολογιστική πολυπλοκότητα. Συνεπώς, στρεφόμαστε προς την ταξινόμηση των διάφορων προβλη-
μάτων σε νέες και πιθανόν ενδιαφέρουσες κλάσεις, καθώς και στην εξαγωγή
κάτω φραγμάτων για συγκεκριμένα προβλήματα. Οι εφαρμοζόμενες τεχνικές
είναι πρωτότυπες και μη-τετριμμένες και σε πολλές περιπτώσεις κατά το παρελθόν είχαν δικαιολογημένα δημιουργήσει προσδοκίες για σημαντική πρόοδο στο συγκεκριμένο πεδίο.
Στα πλαίσια της συγκεκριμένης εργασίας, ορίζεται πρωτίστως το μοντέλο
και οι διάφορες παραλλαγές του, και σε επόμενο στάδιο εξετάζονται ορισμένες από τις τεχνικές που χρησιμοποιούνται στο παρόν επιστημονικό πεδίο. Στη
συνέχεια, περιγράφουμε λεπτομερώς δύο από τα κυριότερα αποτελέσματα στην
περιοχή, αυτό του κάτω φράγματος στη συνάρτηση Ισοτιμίας με τη χρήση του λεγόμενου Λήμματος Εναλλαγής του Håstad καθώς και το σημαντικό αποτέλεσμα του Razborov της εύρεσης ενός κάτω φράγματος για το πρόβλημα της
ΚΛΙΚΑΣ. Το αποτέλεσμα αυτό δημιούργησε μεγάλο ενθουσιασμό κατά το παρελθόν καθώς θεωρήθηκε ως ένα μεγάλο βήμα για την επίλυση του διάσημου
προβλήματος P vs NP. |
| author2 |
Καββαδίας, Δημήτριος |
| author_facet |
Καββαδίας, Δημήτριος Παναγοπούλου, Αγγελική Παναγιώτα |
| format |
Thesis |
| author |
Παναγοπούλου, Αγγελική Παναγιώτα |
| author_sort |
Παναγοπούλου, Αγγελική Παναγιώτα |
| title |
Κυκλωματική πολυπλοκότητα |
| title_short |
Κυκλωματική πολυπλοκότητα |
| title_full |
Κυκλωματική πολυπλοκότητα |
| title_fullStr |
Κυκλωματική πολυπλοκότητα |
| title_full_unstemmed |
Κυκλωματική πολυπλοκότητα |
| title_sort |
κυκλωματική πολυπλοκότητα |
| publishDate |
2016 |
| url |
http://hdl.handle.net/10889/9487 |
| work_keys_str_mv |
AT panagopoulouangelikēpanagiōta kyklōmatikēpolyplokotēta |
| _version_ |
1771297161633333248 |
