Πιθανοτικά ελέγξιμες αποδείξεις

• Main Author: Γεωργόπουλος, Παναγιώτης
• Other Authors: Καββαδίας, Δημήτριος
• Format: Thesis
• Language: Greek
• Published: 2019
• Subjects: Θεώρημα των πιθανοτικά ελέγξιμων αποδείξεων; Πολυπλοκότητα; Probabilistically checkable proofs; Complexity; Hastad; 512.76

Η διπλωματική αυτή αναφέρεται στο Θεώρημα των Πιθανοτικά Ελέγξιμων Αποδείξεων ή Θεώρημα PCP για συντομία (από τα αρχικά του αγγλικού ονόματος του, Probabilistically Checkable Proofs), ένα από τα σημαντικότερα θεωρήματα της Υπολογιστικής Πολυπλοκότητας. Η δομή της διπλωματικής είναι βασισμένη στο...