| Περίληψη: | Η διπλωματική αυτή αναφέρεται στο Θεώρημα των Πιθανοτικά Ελέγξιμων
Αποδείξεων ή Θεώρημα PCP για συντομία (από τα αρχικά του αγγλικού ονόματος του, Probabilistically Checkable Proofs), ένα από τα σημαντικότερα θεωρήματα
της Υπολογιστικής Πολυπλοκότητας. Η δομή της διπλωματικής είναι βασισμένη
στο βιβλίο Computational Complexity των Sanjeev Arora και Boaz Barak.
Η εργασία αυτή αποτελείται από τρία μέρη. Στο πρώτο μέρος θα εισαγάγουμε
βασικές ένοιες που θα χρειαστούν στην συνέχεια καθώς και το τι πραγματεύεται
ουσιαστικά το PCP θεώρημα. (Κεφάλαια 1,2)
Στο δεύτερο μέρος θα αποδείξουμε το κεντρικό PCP θεώρημα καθώς και διάφορες παραλλαγές του. (Κεφάλαια 3,4,5,6,7,8,9)
Στο τρίτο και τελευταίο μέρος γίνεται αναφορά στις συνέπειες της απόδειξης
των PCP θεωρημάτων. (Κεφάλαια 10,11)
Τέλος στο Παράρτημα υπάρχουν αποδείξεις που έχουν παραλειφθεί από το
κύριο μέρος της Απόδειξης ώστε αυτό να γίνει πιο κατανοητό στην ανάγνωση
του.
|
|---|
