Η αλγοριθμική πολυπλοκότητα, (υπολογιστική πολυπλοκότητα ή πολυπλοκότητα Kolmogorov), είναι μια θεμελιώδης ιδέα τόσο στη θεωρία υπολογιστικής πολυπλοκότητας όσο και στη θεωρία αλγοριθμικής πληροφορίας, και παίζει σημαντικό ρόλο στην επίσημη επαγωγή.
Η αλγοριθμική πολυπλοκότητα μιας δυαδικής συμβολοσειράς ορίζεται ως το συντομότερο και πιο αποτελεσματικό πρόγραμμα που μπορεί να παράγει τη συμβολοσειρά. Αν και υπάρχει ένας άπειρος αριθμός προγραμμάτων που μπορούν να παράγουν οποιαδήποτε δεδομένη συμβολοσειρά, ένα πρόγραμμα ή μια ομάδα προγραμμάτων θα είναι πάντα το συντομότερο. Δεν υπάρχει αλγοριθμικός τρόπος εύρεσης του συντομότερου αλγόριθμου που βγάζει μια δεδομένη συμβολοσειρά. αυτό είναι ένα από τα πρώτα αποτελέσματα της θεωρίας της υπολογιστικής πολυπλοκότητας. Ακόμα κι έτσι, μπορούμε να κάνουμε μια μορφωμένη εικασία. Αυτό το αποτέλεσμα, (η υπολογιστική πολυπλοκότητα μιας συμβολοσειράς), αποδεικνύεται πολύ σημαντικό για αποδείξεις που σχετίζονται με την υπολογισιμότητα.
Δεδομένου ότι οποιοδήποτε φυσικό αντικείμενο ή ιδιότητα μπορεί καταρχήν να περιγραφεί σχεδόν σε εξάντληση από μια σειρά από bit, τα αντικείμενα και οι ιδιότητες μπορούν να ειπωθούν ότι έχουν επίσης αλγοριθμική πολυπλοκότητα. Στην πραγματικότητα, η μείωση της πολυπλοκότητας των αντικειμένων του πραγματικού κόσμου σε προγράμματα που παράγουν τα αντικείμενα ως έξοδο, είναι ένας τρόπος προβολής της επιχείρησης της επιστήμης. Τα πολύπλοκα αντικείμενα γύρω μας τείνουν να προέρχονται από τρεις κύριες διαδικασίες παραγωγής. εμφάνιση, εξέλιξη και νοημοσύνη, με τα αντικείμενα που παράγονται από το καθένα να τείνουν προς μεγαλύτερη αλγοριθμική πολυπλοκότητα.
Η υπολογιστική πολυπλοκότητα είναι μια έννοια που χρησιμοποιείται συχνά στη θεωρητική επιστήμη των υπολογιστών για τον προσδιορισμό της σχετικής δυσκολίας υπολογισμού των λύσεων σε μεγάλες κατηγορίες μαθηματικών και λογικών προβλημάτων. Υπάρχουν περισσότερες από 400 κατηγορίες πολυπλοκότητας και ανακαλύπτονται συνεχώς πρόσθετες κατηγορίες. Η περίφημη ερώτηση P = NP αφορά τη φύση δύο από αυτές τις κατηγορίες πολυπλοκότητας. Οι τάξεις πολυπλοκότητας περιλαμβάνουν προβλήματα πολύ πιο δύσκολα από οτιδήποτε μπορεί να αντιμετωπίσει κανείς στα μαθηματικά μέχρι τον λογισμό. Υπάρχουν πολλά προβλήματα που μπορούν να φανταστούν στη θεωρία της υπολογιστικής πολυπλοκότητας που θα απαιτούσαν σχεδόν άπειρο χρόνο για να λυθούν.
Η αλγοριθμική πολυπλοκότητα και οι σχετικές έννοιες αναπτύχθηκαν τη δεκαετία του 1960 από δεκάδες ερευνητές. Ο Andrey Kolmogorov, ο Ray Solomonoff και ο Gregory Chaitin συνέβαλαν σημαντικά στα τέλη της δεκαετίας του ’60 με την αλγοριθμική θεωρία πληροφοριών. Η αρχή του ελάχιστου μήκους μηνύματος, στενά συνδεδεμένη με την αλγοριθμική πολυπλοκότητα, παρέχει μεγάλο μέρος της βάσης των στατιστικών και επαγωγικών συμπερασμάτων και της μηχανικής μάθησης.