Πιθανοτικά ελέγξιμες αποδείξεις
Η διπλωματική αυτή αναφέρεται στο Θεώρημα των Πιθανοτικά Ελέγξιμων Αποδείξεων ή Θεώρημα PCP για συντομία (από τα αρχικά του αγγλικού ονόματος του, Probabilistically Checkable Proofs), ένα από τα σημαντικότερα θεωρήματα της Υπολογιστικής Πολυπλοκότητας. Η δομή της διπλωματικής είναι βασισμένη στο...
| Κύριος συγγραφέας: | |
|---|---|
| Άλλοι συγγραφείς: | |
| Μορφή: | Thesis |
| Γλώσσα: | Greek |
| Έκδοση: |
2019
|
| Θέματα: | |
| Διαθέσιμο Online: | http://hdl.handle.net/10889/12229 |
| id |
nemertes-10889-12229 |
|---|---|
| record_format |
dspace |
| spelling |
nemertes-10889-122292022-09-05T05:39:15Z Πιθανοτικά ελέγξιμες αποδείξεις Γεωργόπουλος, Παναγιώτης Καββαδίας, Δημήτριος Τζερμιάς, Παύλος Μακρή, Ευφροσύνη Καββαδίας, Δημήτριος Georgopoulos, Panagiotis Θεώρημα των πιθανοτικά ελέγξιμων αποδείξεων Πολυπλοκότητα Probabilistically checkable proofs Complexity Hastad 512.76 Η διπλωματική αυτή αναφέρεται στο Θεώρημα των Πιθανοτικά Ελέγξιμων Αποδείξεων ή Θεώρημα PCP για συντομία (από τα αρχικά του αγγλικού ονόματος του, Probabilistically Checkable Proofs), ένα από τα σημαντικότερα θεωρήματα της Υπολογιστικής Πολυπλοκότητας. Η δομή της διπλωματικής είναι βασισμένη στο βιβλίο Computational Complexity των Sanjeev Arora και Boaz Barak. Η εργασία αυτή αποτελείται από τρία μέρη. Στο πρώτο μέρος θα εισαγάγουμε βασικές ένοιες που θα χρειαστούν στην συνέχεια καθώς και το τι πραγματεύεται ουσιαστικά το PCP θεώρημα. (Κεφάλαια 1,2) Στο δεύτερο μέρος θα αποδείξουμε το κεντρικό PCP θεώρημα καθώς και διάφορες παραλλαγές του. (Κεφάλαια 3,4,5,6,7,8,9) Στο τρίτο και τελευταίο μέρος γίνεται αναφορά στις συνέπειες της απόδειξης των PCP θεωρημάτων. (Κεφάλαια 10,11) Τέλος στο Παράρτημα υπάρχουν αποδείξεις που έχουν παραλειφθεί από το κύριο μέρος της Απόδειξης ώστε αυτό να γίνει πιο κατανοητό στην ανάγνωση του. - 2019-06-30T10:45:05Z 2019-06-30T10:45:05Z 2019-03 Thesis http://hdl.handle.net/10889/12229 gr 0 application/pdf |
| institution |
UPatras |
| collection |
Nemertes |
| language |
Greek |
| topic |
Θεώρημα των πιθανοτικά ελέγξιμων αποδείξεων Πολυπλοκότητα Probabilistically checkable proofs Complexity Hastad 512.76 |
| spellingShingle |
Θεώρημα των πιθανοτικά ελέγξιμων αποδείξεων Πολυπλοκότητα Probabilistically checkable proofs Complexity Hastad 512.76 Γεωργόπουλος, Παναγιώτης Πιθανοτικά ελέγξιμες αποδείξεις |
| description |
Η διπλωματική αυτή αναφέρεται στο Θεώρημα των Πιθανοτικά Ελέγξιμων
Αποδείξεων ή Θεώρημα PCP για συντομία (από τα αρχικά του αγγλικού ονόματος του, Probabilistically Checkable Proofs), ένα από τα σημαντικότερα θεωρήματα
της Υπολογιστικής Πολυπλοκότητας. Η δομή της διπλωματικής είναι βασισμένη
στο βιβλίο Computational Complexity των Sanjeev Arora και Boaz Barak.
Η εργασία αυτή αποτελείται από τρία μέρη. Στο πρώτο μέρος θα εισαγάγουμε
βασικές ένοιες που θα χρειαστούν στην συνέχεια καθώς και το τι πραγματεύεται
ουσιαστικά το PCP θεώρημα. (Κεφάλαια 1,2)
Στο δεύτερο μέρος θα αποδείξουμε το κεντρικό PCP θεώρημα καθώς και διάφορες παραλλαγές του. (Κεφάλαια 3,4,5,6,7,8,9)
Στο τρίτο και τελευταίο μέρος γίνεται αναφορά στις συνέπειες της απόδειξης
των PCP θεωρημάτων. (Κεφάλαια 10,11)
Τέλος στο Παράρτημα υπάρχουν αποδείξεις που έχουν παραλειφθεί από το
κύριο μέρος της Απόδειξης ώστε αυτό να γίνει πιο κατανοητό στην ανάγνωση
του. |
| author2 |
Καββαδίας, Δημήτριος |
| author_facet |
Καββαδίας, Δημήτριος Γεωργόπουλος, Παναγιώτης |
| format |
Thesis |
| author |
Γεωργόπουλος, Παναγιώτης |
| author_sort |
Γεωργόπουλος, Παναγιώτης |
| title |
Πιθανοτικά ελέγξιμες αποδείξεις |
| title_short |
Πιθανοτικά ελέγξιμες αποδείξεις |
| title_full |
Πιθανοτικά ελέγξιμες αποδείξεις |
| title_fullStr |
Πιθανοτικά ελέγξιμες αποδείξεις |
| title_full_unstemmed |
Πιθανοτικά ελέγξιμες αποδείξεις |
| title_sort |
πιθανοτικά ελέγξιμες αποδείξεις |
| publishDate |
2019 |
| url |
http://hdl.handle.net/10889/12229 |
| work_keys_str_mv |
AT geōrgopoulospanagiōtēs pithanotikaelenximesapodeixeis |
| _version_ |
1771297145064783872 |
