| Περίληψη: | Σε αυτό το κεφάλαιο παρουσιάζουμε τις βασικές έννοιες της θεωρίας πολυπλοκότητας. Ξεκινάμε με τον ορισμό της μηχανής Turing και κατόπιν δίνουμε τους ορισμούς των βασικών κλάσεων πολυπλοκότητας P, NP, NP-complete, PSPACE κλπ. Επίσης, διατυπώνουμε ένα βασικό πρόβλημα που έχει μεγάλο ενδιαφέρον στην κρυπτογραφία: το πρόβλημα της παραγοντοποίησης. ΄Οπως θα δούμε, αυτό το πρόβλημα ανήκει στην τομή των κλάσεων P και NP. Στο κλασικό μοντέλο υπολογισμού, δηλαδή τη μηχανή Turing, πιστεύουμε ότι το πρόβλημα είναι δύσκολο κατά μέσο όρο. Αν όμως έχουμε στην κατοχή μας έναν κβαντικό υπολογιστή, με αρκετά μεγάλη μνήμη, τότε ο αλγόριθμος του Shor μπορεί να λύσει το πρόβλημα της παραγοντοποίησης σε πολυωνυμικό χρόνο.
|
|---|
