Το EITC/IS/CCTF Computational Complexity Theory Fundamentals είναι το ευρωπαϊκό πρόγραμμα Πιστοποίησης Πληροφορικής σχετικά με θεωρητικές πτυχές των θεμελίων της επιστήμης των υπολογιστών που αποτελούν επίσης βάση της κλασικής ασύμμετρης κρυπτογραφίας δημόσιου κλειδιού που χρησιμοποιείται ευρέως στο Διαδίκτυο.
Το πρόγραμμα σπουδών του EITC/IS/CCTF Computational Complexity Theory Fundamentals καλύπτει θεωρητικές γνώσεις σχετικά με τα θεμέλια της επιστήμης των υπολογιστών και τα υπολογιστικά μοντέλα σε βασικές έννοιες όπως ντετερμινιστικές και μη ντετερμινιστικές μηχανές πεπερασμένης κατάστασης, κανονικές γλώσσες, γραμματιστές χωρίς πλαίσιο και θεωρία γλωσσών, θεωρία αυτόματα, Turing Μηχανές, δυνατότητα επίλυσης προβλημάτων, αναδρομή, λογική και πολυπλοκότητα αλγοριθμικών για θεμελιώδεις εφαρμογές ασφάλειας εντός της ακόλουθης δομής, που περιλαμβάνει ολοκληρωμένο διδακτικό περιεχόμενο βίντεο ως αναφορά για αυτήν την Πιστοποίηση EITC.
Η υπολογιστική πολυπλοκότητα ενός αλγορίθμου είναι η ποσότητα των πόρων που απαιτούνται για τη λειτουργία του. Δίνεται ιδιαίτερη προσοχή στους πόρους χρόνου και μνήμης. Η πολυπλοκότητα ενός προβλήματος ορίζεται ως η πολυπλοκότητα των καλύτερων αλγορίθμων για την επίλυσή του. Η ανάλυση αλγορίθμων είναι η μελέτη της πολυπλοκότητας των ρητά δεδομένων αλγορίθμων, ενώ η υπολογιστική θεωρία πολυπλοκότητας είναι η μελέτη της πολυπλοκότητας των λύσεων προβλημάτων με τους πιο γνωστούς αλγόριθμους. Και οι δύο τομείς είναι αλληλένδετοι επειδή η πολυπλοκότητα ενός αλγορίθμου είναι πάντα ένας ανώτερος περιορισμός στην πολυπλοκότητα του προβλήματος που επιλύει. Επιπλέον, είναι συχνά απαραίτητο να συγκρίνουμε την πολυπλοκότητα ενός συγκεκριμένου αλγορίθμου με την πολυπλοκότητα του προβλήματος που πρέπει να λυθεί κατά την κατασκευή αποτελεσματικών αλγορίθμων. Στις περισσότερες περιπτώσεις, οι μόνες διαθέσιμες πληροφορίες σχετικά με τη δυσκολία ενός προβλήματος είναι ότι είναι μικρότερη από την πολυπλοκότητα των πιο αποτελεσματικών γνωστών τεχνικών. Ως αποτέλεσμα, υπάρχει μεγάλη επικάλυψη μεταξύ της ανάλυσης αλγορίθμων και της θεωρίας πολυπλοκότητας.
Η θεωρία πολυπλοκότητας παίζει σημαντικό ρόλο όχι μόνο στα θεμέλια των υπολογιστικών μοντέλων ως βάση για την επιστήμη των υπολογιστών αλλά και στα θεμέλια της κλασικής ασύμμετρης κρυπτογραφίας (αποκαλούμενη κρυπτογραφία δημόσιου κλειδιού) η οποία είναι ευρέως διαδεδομένη στα σύγχρονα δίκτυα, ειδικά στο Διαδίκτυο. Η κρυπτογράφηση δημόσιου κλειδιού βασίζεται σε υπολογιστικά δύσκολα ορισμένων ασύμμετρων μαθηματικών προβλημάτων όπως για παράδειγμα η παραγοντοποίηση μεγάλων αριθμών στους πρώτους συντελεστές της (αυτή η λειτουργία είναι ένα δύσκολο πρόβλημα στην ταξινόμηση της θεωρίας πολυπλοκότητας, επειδή δεν υπάρχουν γνωστοί αποτελεσματικοί κλασικοί αλγόριθμοι για επίλυση με πόρους που κλιμακώνονται πολυωνυμικά και όχι εκθετικά με την αύξηση του μεγέθους εισόδου του προβλήματος, κάτι που έρχεται σε αντίθεση με μια πολύ απλή αντίστροφη λειτουργία πολλαπλασιασμού σε γνωστούς πρώτους παράγοντες για να δώσει τον αρχικό μεγάλο αριθμό). Χρησιμοποιώντας αυτήν την ασυμμετρία σε μια αρχιτεκτονική της κρυπτογραφίας δημόσιου κλειδιού (καθορίζοντας μια υπολογιστικά ασύμμετρη σχέση μεταξύ του δημόσιου κλειδιού, η οποία μπορεί να υπολογιστεί εύκολα από ένα ιδιωτικό κλειδί, ενώ το ιδιωτικό κλειδί δεν μπορεί να είναι εύκολα υπολογιστής από ένα δημόσιο κλειδί, μπορεί κανείς να ανακοινώνει το δημόσιο κλειδί και επιτρέπει σε άλλες πλευρές επικοινωνίας να το χρησιμοποιούν για ασύμμετρη κρυπτογράφηση δεδομένων, τα οποία μπορούν να αποκρυπτογραφηθούν μόνο με το συζευγμένο ιδιωτικό κλειδί, μη διαθέσιμο υπολογιστικά σε τρίτους, καθιστώντας έτσι την επικοινωνία ασφαλή).
Η θεωρία της υπολογιστικής πολυπλοκότητας αναπτύχθηκε κυρίως σε επιτεύγματα πρωτοπόρων της επιστήμης των υπολογιστών και των αλγοριθμικών, όπως ο Άλαν Τούρινγκ, το έργο του οποίου ήταν κρίσιμο για τη διάρρηξη του κωδικού Enigma της Ναζιστικής Γερμανίας, που έπαιξε βαθύ ρόλο στη νίκη των συμμάχων στον Δεύτερο Παγκόσμιο Πόλεμο. Η κρυπτανάλυση με στόχο την επινόηση και την αυτοματοποίηση των υπολογιστικών διαδικασιών ανάλυσης δεδομένων (κυρίως κρυπτογραφημένης επικοινωνίας) για την αποκάλυψη των κρυμμένων πληροφοριών χρησιμοποιήθηκε για την παραβίαση κρυπτογραφικών συστημάτων και την πρόσβαση στα περιεχόμενα κρυπτογραφημένης επικοινωνίας, συνήθως στρατηγικής στρατιωτικής σημασίας. Ήταν επίσης η κρυπτανάλυση που κατέλυσε την ανάπτυξη των πρώτων σύγχρονων υπολογιστών (οι οποίοι αρχικά εφαρμόστηκαν σε έναν στρατηγικό στόχο της διάσπασης κώδικα). Προηγήθηκε του Βρετανικού Κολοσσού (που θεωρείται ο πρώτος σύγχρονος ηλεκτρονικός και προγραμματικός υπολογιστής) η πολωνική «βόμβα», μια ηλεκτρονική υπολογιστική συσκευή που σχεδιάστηκε από τον Marian Rejewski για να βοηθήσει στο σπάσιμο των κρυπτογράφησης Enigma, και παραδόθηκε στη Μεγάλη Βρετανία από την πολωνική υπηρεσία πληροφοριών μαζί με η συλληφθείσα γερμανική μηχανή κρυπτογράφησης Enigma, μετά την εισβολή της Γερμανίας στην Πολωνία το 1939. Με βάση αυτή τη συσκευή, ο Alan Turing ανέπτυξε το πιο προηγμένο αντίστοιχό του για να διακόψει με επιτυχία τη γερμανική κρυπτογραφημένη επικοινωνία, η οποία αργότερα εξελίχθηκε σε σύγχρονους υπολογιστές.
Επειδή η ποσότητα των πόρων που απαιτούνται για την εκτέλεση ενός αλγορίθμου ποικίλλει ανάλογα με το μέγεθος της εισόδου, η πολυπλοκότητα εκφράζεται συνήθως ως συνάρτηση f(n), όπου n είναι το μέγεθος εισόδου και f(n) είναι είτε η πολυπλοκότητα στη χειρότερη περίπτωση ( η μέγιστη ποσότητα πόρων που απαιτούνται για όλες τις εισροές μεγέθους n) ή η πολυπλοκότητα της μέσης περίπτωσης (ο μέσος όρος της ποσότητας πόρων σε όλες τις εισροές μεγέθους n). Ο αριθμός των απαιτούμενων στοιχειωδών λειτουργιών σε μια είσοδο μεγέθους n δηλώνεται συνήθως ως πολυπλοκότητα χρόνου, όπου πιστεύεται ότι οι στοιχειώδεις λειτουργίες χρειάζονται σταθερό χρόνο σε έναν συγκεκριμένο υπολογιστή και αλλάζουν μόνο κατά σταθερό παράγοντα όταν εκτελούνται σε διαφορετικό μηχάνημα. Η ποσότητα μνήμης που απαιτείται από έναν αλγόριθμο σε μια είσοδο μεγέθους n είναι γνωστή ως πολυπλοκότητα χώρου.
Ο χρόνος είναι ο πιο συνηθισμένος πόρος. Όταν ο όρος «πολυπλοκότητα» χρησιμοποιείται χωρίς προσδιορισμό, συνήθως αναφέρεται στην πολυπλοκότητα του χρόνου.
Οι παραδοσιακές μονάδες χρόνου (δευτερόλεπτα, λεπτά και ούτω καθεξής) δεν χρησιμοποιούνται στη θεωρία πολυπλοκότητας, καθώς εξαρτώνται υπερβολικά από τον επιλεγμένο υπολογιστή και την πρόοδο της τεχνολογίας. Για παράδειγμα, ένας υπολογιστής σήμερα μπορεί να εκτελέσει έναν αλγόριθμο πολύ πιο γρήγορα από έναν υπολογιστή της δεκαετίας του 1960, ωστόσο, αυτό οφείλεται σε τεχνολογικές ανακαλύψεις στο υλικό του υπολογιστή και όχι σε εγγενή ποιότητα του αλγορίθμου. Ο στόχος της θεωρίας πολυπλοκότητας είναι να ποσοτικοποιήσει τις εγγενείς χρονικές ανάγκες των αλγορίθμων ή τους θεμελιώδεις χρονικούς περιορισμούς που θα επιβάλει ένας αλγόριθμος σε οποιονδήποτε υπολογιστή. Αυτό επιτυγχάνεται μετρώντας πόσες βασικές λειτουργίες εκτελούνται κατά τη διάρκεια του υπολογισμού. Αυτές οι διαδικασίες αναφέρονται συνήθως ως βήματα επειδή θεωρείται ότι χρειάζονται σταθερό χρόνο σε ένα συγκεκριμένο μηχάνημα (δηλαδή, δεν επηρεάζονται από την ποσότητα της εισόδου).
Ένας άλλος κρίσιμος πόρος είναι η ποσότητα της μνήμης του υπολογιστή που απαιτείται για την εκτέλεση αλγορίθμων.
Ένας άλλος πόρος που χρησιμοποιείται συχνά είναι ο αριθμός των αριθμητικών πράξεων. Σε αυτό το σενάριο, χρησιμοποιείται ο όρος «αριθμητική πολυπλοκότητα». Η χρονική πολυπλοκότητα είναι γενικά το γινόμενο της αριθμητικής πολυπλοκότητας με έναν σταθερό παράγοντα, εάν είναι γνωστός ένας ανώτερος περιορισμός στο μέγεθος της δυαδικής αναπαράστασης των αριθμών που εμφανίζονται κατά τη διάρκεια ενός υπολογισμού.
Το μέγεθος των ακεραίων που χρησιμοποιούνται κατά τη διάρκεια ενός υπολογισμού δεν περιορίζεται για πολλές μεθόδους και δεν είναι ρεαλιστικό να υποθέσουμε ότι οι αριθμητικές πράξεις απαιτούν ένα σταθερό χρονικό διάστημα. Ως αποτέλεσμα, η χρονική πολυπλοκότητα, γνωστή και ως πολυπλοκότητα bit, μπορεί να είναι σημαντικά υψηλότερη από την αριθμητική πολυπλοκότητα. Η αριθμητική δυσκολία του υπολογισμού της ορίζουσας ενός nn ακέραιου πίνακα, για παράδειγμα, είναι O(n^3) για τυπικές τεχνικές (Gaussian elimination). Επειδή το μέγεθος των συντελεστών μπορεί να επεκταθεί εκθετικά κατά τη διάρκεια του υπολογισμού, η πολυπλοκότητα bit των ίδιων μεθόδων είναι εκθετική σε n. Εάν αυτές οι τεχνικές χρησιμοποιούνται σε συνδυασμό με πολυ-αρθρωτή αριθμητική, η πολυπλοκότητα των bit μπορεί να μειωθεί σε O(n^4).
Η πολυπλοκότητα bit, με τυπικούς όρους, αναφέρεται στον αριθμό των λειτουργιών σε bit που απαιτούνται για την εκτέλεση ενός αλγόριθμου. Ισοδυναμεί με τη χρονική πολυπλοκότητα έως έναν σταθερό παράγοντα στα περισσότερα μοντέλα υπολογισμού. Ο αριθμός των λειτουργιών σε λέξεις μηχανής που απαιτούνται από τους υπολογιστές είναι ανάλογος της πολυπλοκότητας των bit. Για ρεαλιστικά μοντέλα υπολογισμού, η χρονική πολυπλοκότητα και η πολυπλοκότητα bit είναι επομένως πανομοιότυπα.
Ο πόρος που λαμβάνεται συχνά υπόψη κατά την ταξινόμηση και την αναζήτηση είναι ο αριθμός των συγκρίσεων εγγραφών. Εάν τα δεδομένα είναι καλά τακτοποιημένα, αυτό είναι ένας καλός δείκτης της χρονικής πολυπλοκότητας.
Σε όλες τις πιθανές εισόδους, η μέτρηση του αριθμού των βημάτων σε έναν αλγόριθμο είναι αδύνατη. Επειδή η πολυπλοκότητα μιας εισόδου αυξάνεται με το μέγεθός της, αναπαρίσταται συνήθως ως συνάρτηση του μεγέθους n της εισόδου (σε bit), και έτσι η πολυπλοκότητα είναι συνάρτηση του n. Ωστόσο, για τις εισόδους ίδιου μεγέθους, η πολυπλοκότητα ενός αλγορίθμου μπορεί να ποικίλλει σημαντικά. Ως αποτέλεσμα, μια ποικιλία συναρτήσεων πολυπλοκότητας χρησιμοποιείται συνήθως.
Η πολυπλοκότητα στη χειρότερη περίπτωση είναι το άθροισμα όλης της πολυπλοκότητας για όλες τις εισόδους μεγέθους n, ενώ η πολυπλοκότητα της μέσης περίπτωσης είναι το άθροισμα όλης της πολυπλοκότητας για όλες τις εισόδους μεγέθους n (αυτό είναι λογικό, καθώς ο αριθμός των πιθανών εισόδων ενός δεδομένου μεγέθους είναι πεπερασμένος). Όταν χρησιμοποιείται ο όρος «πολυπλοκότητα» χωρίς περαιτέρω ορισμό, λαμβάνεται υπόψη η χρονική πολυπλοκότητα στη χειρότερη περίπτωση.
Η πολυπλοκότητα της χειρότερης και της μέσης περίπτωσης είναι εμφανώς δύσκολο να υπολογιστούν σωστά. Επιπλέον, αυτές οι ακριβείς τιμές έχουν ελάχιστη πρακτική εφαρμογή, επειδή οποιαδήποτε αλλαγή στο μοντέλο μηχανής ή υπολογισμού θα διαφοροποιούσε ελαφρώς την πολυπλοκότητα. Επιπλέον, η χρήση πόρων δεν είναι κρίσιμη για μικρές τιμές του n, επομένως η ευκολία υλοποίησης είναι συχνά πιο ελκυστική από τη χαμηλή πολυπλοκότητα για τα μικρά n.
Για αυτούς τους λόγους, δίνεται μεγαλύτερη προσοχή στη συμπεριφορά της πολυπλοκότητας για το υψηλό n, δηλαδή στην ασυμπτωτική συμπεριφορά του καθώς το n πλησιάζει το άπειρο. Ως αποτέλεσμα, ο μεγάλος συμβολισμός O χρησιμοποιείται συνήθως για να υποδείξει την πολυπλοκότητα.
Υπολογιστικά μοντέλα
Η επιλογή ενός υπολογιστικού μοντέλου, το οποίο συνίσταται στον προσδιορισμό των βασικών πράξεων που εκτελούνται σε μια μονάδα χρόνου, είναι κρίσιμη για τον προσδιορισμό της πολυπλοκότητας. Αυτό μερικές φορές αναφέρεται ως μηχανή Turing πολλαπλών ταινιών όταν το υπολογιστικό παράδειγμα δεν περιγράφεται συγκεκριμένα.
Ένα ντετερμινιστικό μοντέλο υπολογισμού είναι αυτό στο οποίο οι επόμενες καταστάσεις της μηχανής και οι λειτουργίες που πρέπει να εκτελεστούν ορίζονται εξ ολοκλήρου από την προηγούμενη κατάσταση. Οι αναδρομικές συναρτήσεις, ο λογισμός λάμδα και οι μηχανές Turing ήταν τα πρώτα ντετερμινιστικά μοντέλα. Οι μηχανές τυχαίας πρόσβασης (γνωστές και ως μηχανές RAM) είναι ένα δημοφιλές παράδειγμα για την προσομοίωση υπολογιστών πραγματικού κόσμου.
Όταν το υπολογιστικό μοντέλο δεν έχει καθοριστεί, συνήθως υποτίθεται ότι η μηχανή Turing πολλαπλών ταινιών. Στις μηχανές Turing πολλαπλών ταινιών, η χρονική πολυπλοκότητα είναι η ίδια όπως στις μηχανές RAM για τους περισσότερους αλγόριθμους, αν και μπορεί να απαιτείται μεγάλη προσοχή στον τρόπο αποθήκευσης δεδομένων στη μνήμη για να επιτευχθεί αυτή η ισοδυναμία.
Μπορούν να γίνουν διάφορες επιλογές σε ορισμένα στάδια του υπολογισμού σε ένα μη ντετερμινιστικό μοντέλο υπολογισμού, όπως οι μη ντετερμινιστικές μηχανές Turing. Στη θεωρία της πολυπλοκότητας, όλες οι εφικτές επιλογές εξετάζονται ταυτόχρονα και η μη ντετερμινιστική χρονική πολυπλοκότητα είναι ο χρόνος που απαιτείται όταν γίνονται πάντα οι καλύτερες επιλογές. Για να το θέσω αλλιώς, ο υπολογισμός γίνεται ταυτόχρονα σε όσους (πανομοιότυπους) επεξεργαστές απαιτούνται και ο μη ντετερμινιστικός χρόνος υπολογισμού είναι ο χρόνος που χρειάζεται ο πρώτος επεξεργαστής για να ολοκληρώσει τον υπολογισμό. Αυτός ο παραλληλισμός μπορεί να χρησιμοποιηθεί στον κβαντικό υπολογισμό χρησιμοποιώντας υπέρθετες εμπλεκόμενες καταστάσεις κατά την εκτέλεση εξειδικευμένων κβαντικών αλγορίθμων, όπως η παραγοντοποίηση μικροσκοπικών ακεραίων από τον Shor για παράδειγμα.
Ακόμα κι αν ένα τέτοιο υπολογιστικό μοντέλο δεν είναι επί του παρόντος πρακτικό, έχει θεωρητική σημασία, ιδιαίτερα σε σχέση με το πρόβλημα P = NP, το οποίο ρωτά εάν οι τάξεις πολυπλοκότητας που παράγονται χρησιμοποιώντας τον «πολυωνυμικό χρόνο» και τον «μη ντετερμινιστικό πολυωνυμικό χρόνο» ως ελάχιστα ανώτερες τα όρια είναι ίδια. Σε έναν ντετερμινιστικό υπολογιστή, η προσομοίωση ενός αλγόριθμου NP απαιτεί "εκθετικό χρόνο". Εάν μια εργασία μπορεί να λυθεί σε πολυωνυμικό χρόνο σε ένα μη ντετερμινιστικό σύστημα, ανήκει στην κατηγορία δυσκολίας NP. Εάν ένα ζήτημα βρίσκεται στο NP και δεν είναι ευκολότερο από οποιοδήποτε άλλο πρόβλημα NP, λέγεται ότι είναι NP-complete. Το πρόβλημα του σακιδίου, το πρόβλημα του ταξιδιώτη πωλητή και το πρόβλημα ικανοποίησης Boolean είναι όλα συνδυαστικά προβλήματα με πλήρη NP. Ο πιο γνωστός αλγόριθμος έχει εκθετική πολυπλοκότητα για όλα αυτά τα προβλήματα. Εάν οποιοδήποτε από αυτά τα ζητήματα μπορούσε να λυθεί σε πολυωνυμικό χρόνο σε μια ντετερμινιστική μηχανή, τότε όλα τα προβλήματα NP θα μπορούσαν να λυθούν σε πολυωνυμικό χρόνο επίσης και θα δημιουργηθεί P = NP. Από το 2017, θεωρείται ευρέως ότι το P NP, υπονοώντας ότι οι χειρότερες καταστάσεις προβλημάτων NP είναι θεμελιωδώς δύσκολο να επιλυθούν, δηλαδή χρειάζονται πολύ μεγαλύτερο χρονικό διάστημα από οποιοδήποτε εφικτό χρονικό διάστημα (δεκαετίες) δεδομένου ενδιαφέροντος μήκους εισόδου.
Παράλληλος και κατανεμημένος υπολογισμός
Ο παράλληλος και κατανεμημένος υπολογισμός περιλαμβάνει τη διαίρεση της επεξεργασίας σε πολλούς επεξεργαστές που λειτουργούν όλοι ταυτόχρονα. Η θεμελιώδης διάκριση μεταξύ των διαφόρων μοντέλων είναι η μέθοδος αποστολής δεδομένων μεταξύ των επεξεργαστών. Η μετάδοση δεδομένων μεταξύ των επεξεργαστών είναι συνήθως πολύ γρήγορη στον παράλληλο υπολογισμό, ενώ η μεταφορά δεδομένων μεταξύ των επεξεργαστών σε κατανεμημένους υπολογισμούς γίνεται σε ένα δίκτυο και επομένως είναι σημαντικά πιο αργή.
Ένας υπολογισμός σε N επεξεργαστές παίρνει τουλάχιστον το πηλίκο κατά N του χρόνου που χρειάζεται σε έναν μόνο επεξεργαστή. Στην πραγματικότητα, επειδή ορισμένες δευτερεύουσες εργασίες δεν μπορούν να παραλληλιστούν και ορισμένοι επεξεργαστές μπορεί να χρειαστεί να περιμένουν ένα αποτέλεσμα από έναν άλλο επεξεργαστή, αυτό το θεωρητικά ιδανικό όριο δεν θα επιτευχθεί ποτέ.
Το βασικό ζήτημα πολυπλοκότητας είναι επομένως η ανάπτυξη αλγορίθμων έτσι ώστε το γινόμενο του υπολογιστικού χρόνου με τον αριθμό των επεξεργαστών να είναι όσο το δυνατόν πιο κοντά στον χρόνο που απαιτείται για την εκτέλεση του ίδιου υπολογισμού σε έναν μόνο επεξεργαστή.
Κβαντικός υπολογισμός
Ένας κβαντικός υπολογιστής είναι ένας υπολογιστής με ένα υπολογιστικό μοντέλο που βασίζεται στην κβαντική μηχανική. Η θέση Church–Turing ισχύει για τους κβαντικούς υπολογιστές, υπονοώντας ότι οποιοδήποτε ζήτημα μπορεί να λύσει ένας κβαντικός υπολογιστής μπορεί επίσης να λυθεί από μια μηχανή Turing. Ωστόσο, ορισμένες εργασίες μπορεί θεωρητικά να επιλυθούν χρησιμοποιώντας έναν κβαντικό υπολογιστή αντί για έναν κλασικό υπολογιστή με σημαντικά χαμηλότερη χρονική πολυπλοκότητα. Προς το παρόν, αυτό είναι αυστηρά θεωρητικό, καθώς κανείς δεν ξέρει πώς να αναπτύξει έναν πρακτικό κβαντικό υπολογιστή.
Η κβαντική θεωρία πολυπλοκότητας δημιουργήθηκε για να διερευνήσει τους διαφορετικούς τύπους ζητημάτων που μπορούν να επιλυθούν από τους κβαντικούς υπολογιστές. Χρησιμοποιείται στη μετακβαντική κρυπτογραφία, η οποία είναι η διαδικασία δημιουργίας κρυπτογραφικών πρωτοκόλλων που είναι ανθεκτικά σε επιθέσεις κβαντικού υπολογιστή.
Πολυπλοκότητα του προβλήματος (κάτω όρια)
Η ελάχιστη πολυπλοκότητα των αλγορίθμων που μπορεί να λύσουν το πρόβλημα, συμπεριλαμβανομένων των μη ανακαλυφθεισών τεχνικών, είναι η πολυπλοκότητα του προβλήματος. Ως αποτέλεσμα, η πολυπλοκότητα ενός προβλήματος είναι ίση με την πολυπλοκότητα οποιουδήποτε αλγορίθμου που το λύνει.
Ως αποτέλεσμα, οποιαδήποτε πολυπλοκότητα δίνεται με μεγάλη συμβολογραφία Ο αντιπροσωπεύει μια πολυπλοκότητα τόσο του αλγορίθμου όσο και του συνοδευτικού προβλήματος.
Από την άλλη πλευρά, η απόκτηση μη τετριμμένων κατώτερων ορίων για την πολυπλοκότητα του ζητήματος είναι συχνά δύσκολη και υπάρχουν λίγες στρατηγικές για να γίνει αυτό.
Προκειμένου να επιλυθούν τα περισσότερα ζητήματα, πρέπει να διαβαστούν όλα τα δεδομένα εισόδου, κάτι που απαιτεί χρόνο ανάλογο με το μέγεθος των δεδομένων. Ως αποτέλεσμα, τέτοια προβλήματα έχουν τουλάχιστον γραμμική πολυπλοκότητα ή, σε μεγάλους ωμέγα συμβολισμούς, πολυπλοκότητα Ω(n).
Ορισμένα προβλήματα, όπως αυτά της άλγεβρας υπολογιστών και της υπολογιστικής αλγεβρικής γεωμετρίας, έχουν πολύ μεγάλες λύσεις. Επειδή η έξοδος πρέπει να γραφτεί, η πολυπλοκότητα περιορίζεται από το μέγιστο μέγεθος της εξόδου.
Ο αριθμός των συγκρίσεων που απαιτούνται για έναν αλγόριθμο ταξινόμησης έχει μη γραμμικό κάτω όριο Ω(nlogn). Ως αποτέλεσμα, οι καλύτεροι αλγόριθμοι ταξινόμησης είναι οι πιο αποτελεσματικοί αφού η πολυπλοκότητά τους είναι O(nlogn). Το γεγονός ότι υπάρχουν ν! τρόποι οργάνωσης n πραγμάτων οδηγεί σε αυτό το κατώτερο όριο. Επειδή κάθε σύγκριση χωρίζει αυτή τη συλλογή των n! παραγγελίες σε δύο κομμάτια, ο αριθμός των N συγκρίσεων που απαιτούνται για τη διάκριση όλων των παραγγελιών πρέπει να είναι 2N > n!, υπονοώντας O(nlogn) με τον τύπο του Stirling.
Η μείωση ενός προβλήματος σε άλλο πρόβλημα είναι μια κοινή στρατηγική για τη λήψη περιορισμών μειωμένης πολυπλοκότητας.
Ανάπτυξη αλγορίθμου
Η αξιολόγηση της πολυπλοκότητας ενός αλγορίθμου είναι ένα σημαντικό στοιχείο της διαδικασίας σχεδιασμού, καθώς παρέχει χρήσιμες πληροφορίες σχετικά με την απόδοση που μπορεί να αναμένεται.
Είναι μια συχνή παρανόηση ότι, ως αποτέλεσμα του νόμου του Moore, ο οποίος προβλέπει την εκθετική αύξηση της ισχύος των σύγχρονων υπολογιστών, η αξιολόγηση της πολυπλοκότητας των αλγορίθμων θα γίνει λιγότερο σχετική. Αυτό είναι λανθασμένο επειδή η αυξημένη ισχύς επιτρέπει την επεξεργασία τεράστιων ποσοτήτων δεδομένων (μεγάλα δεδομένα). Για παράδειγμα, οποιοσδήποτε αλγόριθμος θα πρέπει να λειτουργεί καλά σε λιγότερο από ένα δευτερόλεπτο όταν ταξινομεί αλφαβητικά μια λίστα με μερικές εκατοντάδες καταχωρήσεις, όπως η βιβλιογραφία ενός βιβλίου. Από την άλλη πλευρά, για ένα εκατομμύριο καταχωρήσεις (για παράδειγμα, οι αριθμοί τηλεφώνου μιας μεγάλης πόλης), οι βασικοί αλγόριθμοι που απαιτούν συγκρίσεις O(n2) θα έπρεπε να εκτελέσουν ένα τρισεκατομμύριο συγκρίσεις, οι οποίες θα χρειάζονταν τρεις ώρες με ταχύτητα 10 εκατομμύρια συγκρίσεις ανά δευτερόλεπτο. Η γρήγορη ταξινόμηση και η συγχώνευση, από την άλλη πλευρά, απαιτούν μόνο συγκρίσεις nlogn (ως πολυπλοκότητα μέσης περίπτωσης για την πρώτη, ως πολυπλοκότητα στη χειρότερη περίπτωση για τη δεύτερη). Αυτό παράγει περίπου 30,000,000 συγκρίσεις για n = 1,000,000, κάτι που θα χρειαζόταν μόνο 3 δευτερόλεπτα σε 10 εκατομμύρια συγκρίσεις ανά δευτερόλεπτο.
Ως αποτέλεσμα, η αξιολόγηση της πολυπλοκότητας μπορεί να επιτρέψει την εξάλειψη πολλών αναποτελεσματικών αλγορίθμων πριν από την εφαρμογή. Αυτό μπορεί επίσης να χρησιμοποιηθεί για την τελειοποίηση πολύπλοκων αλγορίθμων χωρίς να χρειάζεται να δοκιμάσετε όλες τις πιθανές παραλλαγές. Η μελέτη της πολυπλοκότητας επιτρέπει την εστίαση της προσπάθειας για αύξηση της αποτελεσματικότητας μιας υλοποίησης με τον προσδιορισμό των πιο δαπανηρών βημάτων ενός πολύπλοκου αλγορίθμου.
Για να εξοικειωθείτε λεπτομερώς με το πρόγραμμα σπουδών πιστοποίησης, μπορείτε να επεκτείνετε και να αναλύσετε τον παρακάτω πίνακα.
Το Πρόγραμμα Σπουδών Πιστοποίησης Βασικών Θεωριών Υπολογιστικής Πολυπλοκότητας EITC/IS/CCTF αναφέρεται σε διδακτικό υλικό ανοικτής πρόσβασης σε μορφή βίντεο. Η μαθησιακή διαδικασία χωρίζεται σε μια δομή βήμα προς βήμα (προγράμματα -> μαθήματα -> θέματα) που καλύπτει σχετικά μέρη του προγράμματος σπουδών. Παρέχονται επίσης απεριόριστες συμβουλές με ειδικούς στον τομέα.
Για λεπτομέρειες σχετικά με τη διαδικασία πιστοποίησης ελέγξτε Πως δουλεύει.
Υλικό ανάγνωσης πρωτοβάθμιας υποστηρικτικού προγράμματος σπουδών
S. Arora, B. Barak, Computational Complexity: A Modern Approach
https://theory.cs.princeton.edu/complexity/book.pdf
Υλικό ανάγνωσης δευτεροβάθμιας υποστήριξης προγράμματος σπουδών
O. Goldreich, Εισαγωγή στη Θεωρία της Πολυπλοκότητας:
https://www.wisdom.weizmann.ac.il/~oded/cc99.html
Υποστηρικτικό αναγνωστικό υλικό για τα διακριτά μαθηματικά
J. Aspnes, Notes on Discrete Mathematics:
https://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf
Υποστηρικτικό αναγνωστικό υλικό για τη θεωρία γραφημάτων
R. Diestel, Θεωρία Γραφημάτων:
https://diestel-graph-theory.com/
Κατεβάστε το πλήρες προπαρασκευαστικό υλικό αυτομάθησης εκτός σύνδεσης για το πρόγραμμα EITC/IS/CCTF Computational Complexity Theory Fundamentals σε αρχείο PDF
Προπαρασκευαστικά υλικά EITC/IS/CCTF – τυπική έκδοση
Προπαρασκευαστικό υλικό EITC/IS/CCTF – εκτεταμένη έκδοση με ερωτήσεις αναθεώρησης