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: 2022
Item Details:
License: Attribution - NonCommercial - ShareAlike 4.0 International (CC BY-NC-SA 4.0)
Handle http://hdl.handle.net/11419/8188
Bibliographic Citation: Draziotis, K. (2022). Complexity & Turing Machines [Chapter]. In Draziotis, K. 2022. Introduction to Cryptography [Undergraduate textbook]. Kallipos, Open Academic Editions. chapter 7. http://hdl.handle.net/11419/8188
Language: Greek
Is Part of: Introduction to Cryptography
Publication Origin: Kallipos, Open Academic Editions