Κωδικοποίηση Πιθανοτικώς Ελέγξιμων Αποδείξεων

Abstract

Τη δεκαετία του 1990, αποδείχτηκε ένα θεώρημα εξαιρετικής σημασίας στη θεωρία πολυπλοκότητας. Συγκεκριμένα, υπάρχει τρόπος κωδικοποίησης των αποδείξεων και ελέγχου της ορθότητάς τους, τέτοιος ώστε ο επαληθευτής να διαβάζει 3 μόνο δυαδικά ψηφία tης απόδειξης και να αποκτά πιθανοτική αυτοπεποίθηση για την ισχύ της. Ακόμη, ο νέος αυτός τρόπος κωδικοποίησης αρκεί να έχει μόνο πολυωνυμικά μεγαλύτερο μέγεθος από αυτό της αρχικής απόδειξης. Θα εστιάσουμε σε ένα λιγότερα ισχυρό αποτέλεσμα, το οποίο αποκαλείται το PCP θεώρημα (θεώρημα Πιθανοτικώς Ελέγξιμων Αποδείξεων), στις οποίες ο επαληθευτής χρησιμοποιεί λογαριθμική τυχαιότητα και αναζητά ένα σταθερό αριθμό δυαδικών ψηφίων στην απόδειξη.Η πρώτη απόδειξη του θεωρήματος συνδύασε προηγούμενα αποτελέσματα πάνω σε διάφορες αλγεβρικές τεχνικές και λίγο αργότερα ο Hastad παρουσίασε τον επαληθευτή των 3 δυαδικών ψηφίων που αναφέραμε προηγουμένως. ΤΟ 2005, η Irit Dinur έδωσε μια συνδυαστική απόδειξη του θεωρήματος. Ο κύριος στόχος αυτής της διπλωματικής εργασίας είναι η μελέτη της απόδειξης της Dinur. Από αυτή τη σκοπιά, θα επικεντρωθούμε στους τομείς που απαιτούνται για την κατανόηση της απόδειξης, μεταξύ των οποίων είναι οι επεκτατικοί γράφοι και η κωδικοποίηση κατά Hadamard.