Adobe PDF
(1.27 MB)
| Title Details: | |
|
Complexity & Turing Machines |
|
| Authors: |
Draziotis, Konstantinos |
| Description: | |
| Abstract: |
Σε αυτό το κεφάλαιο παρουσιάζουμε τις βασικές έννοιες της θεωρίας πολυπλοκότητας. Ξεκινάμε με τον ορισμό της μηχανής Turing και κατόπιν δίνουμε τους ορισμούς των βασικών κλάσεων πολυπλοκότητας P, NP, NP-complete, PSPACE κλπ. Επίσης, διατυπώνουμε ένα βασικό πρόβλημα που έχει μεγάλο ενδιαφέρον στην κρυπτογραφία: το πρόβλημα της παραγοντοποίησης. ΄Οπως θα δούμε, αυτό το πρόβλημα ανήκει στην τομή των κλάσεων P και NP. Στο κλασικό μοντέλο υπολογισμού, δηλαδή τη μηχανή Turing, πιστεύουμε ότι το πρόβλημα είναι δύσκολο κατά μέσο όρο. Αν όμως έχουμε στην κατοχή μας έναν κβαντικό υπολογιστή, με αρκετά μεγάλη μνήμη, τότε ο αλγόριθμος του Shor μπορεί να λύσει το πρόβλημα της παραγοντοποίησης σε πολυωνυμικό χρόνο.
|
| Linguistic Editors: |
Triantafyllidou, Georgia |
| Technical Editors: |
Draziotis, Konstantinos |
| Graphic Editors: |
Draziotis, Konstantinos |
| Type: |
Chapter |
| Creation Date: | 16-03-2022 |
| Item Details: | |
| License: |
Attribution - NonCommercial - ShareAlike 4.0 International (CC BY-NC-SA 4.0) |
| Handle | http://hdl.handle.net/11419/8188 |
| Bibliographic Reference: | Draziotis, K. (2022). Complexity & Turing Machines [Chapter]. In Draziotis, K. 2022. Introduction to Cryptography [Undergraduate textbook]. Kallipos, Open Academic Editions. https://hdl.handle.net/11419/8188 |
| Language: |
Greek |
| Is Part of: |
Introduction to Cryptography |
| Publication Origin: |
Kallipos, Open Academic Editions |