Τι είναι η αλγοριθμική πολυπλοκότητα;

Η αλγοριθμική πολυπλοκότητα, (υπολογιστική πολυπλοκότητα ή η πολυπλοκότητα του Kolmogorov), είναι μια θεμελιώδη ιδέα τόσο στη θεωρία της υπολογιστικής πολυπλοκότητας και αλγοριθμικής θεωρίας πληροφοριών και παίζει σημαντικό ρόλο στην επίσημη επαγωγή.

Η αλγοριθμική πολυπλοκότητα μιας δυαδικής χορδής ορίζεται ως το συντομότερο και πιο αποτελεσματικό πρόγραμμα που μπορεί να παράγει τη συμβολοσειρά.Αν και υπάρχει ένας άπειρος αριθμός προγραμμάτων που μπορούν να παράγουν οποιαδήποτε συγκεκριμένη συμβολοσειρά, ένα πρόγραμμα ή μια ομάδα προγραμμάτων θα είναι πάντα το συντομότερο.Δεν υπάρχει αλγοριθμικός τρόπος εύρεσης του συντομότερου αλγορίθμου που εξάγει μια δεδομένη συμβολοσειρά.Αυτό είναι ένα από τα πρώτα αποτελέσματα της θεωρίας υπολογιστικής πολυπλοκότητας.Παρόλα αυτά, μπορούμε να κάνουμε μια εκπαιδευμένη εικασία.Αυτό το αποτέλεσμα, (η υπολογιστική πολυπλοκότητα μιας συμβολοσειράς), αποδεικνύεται πολύ σημαντική για τις αποδείξεις που σχετίζονται με την υπολογιστική ικανότητα. Δεδομένου ότι οποιοδήποτε φυσικό αντικείμενο ή ιδιοκτησία μπορεί κατ 'αρχήν να περιγραφεί σε σχεδόν εξουσία από μια σειρά από κομμάτια, αντικείμενα και ιδιότητεςΜπορεί να ειπωθεί ότι έχει επίσης αλγοριθμική πολυπλοκότητα.Στην πραγματικότητα, η μείωση της πολυπλοκότητας των αντικειμένων πραγματικού κόσμου σε προγράμματα που παράγουν τα αντικείμενα ως παραγωγή, είναι ένας τρόπος για την προβολή της επιχείρησης της επιστήμης.Τα σύνθετα αντικείμενα γύρω μας τείνουν να προέρχονται από τρεις διαδικασίες κύριας παραγωγής.

Η υπολογιστική πολυπλοκότητα είναι μια έννοια που χρησιμοποιείται συχνά στη θεωρητική επιστήμη των υπολογιστών για τον προσδιορισμό της σχετικής δυσκολίας υπολογισμού των διαλυμάτων σε ευρείες τάξειςτων μαθηματικών και λογικών προβλημάτων.Υπάρχουν περισσότερες από 400 κλάσεις πολυπλοκότητας και συνεχώς ανακαλύπτονται πρόσθετες κατηγορίες.Το διάσημο p ' np Ερώτηση αφορά τη φύση δύο από αυτές τις κατηγορίες πολυπλοκότητας.Οι τάξεις πολυπλοκότητας περιλαμβάνουν προβλήματα πολύ πιο δύσκολα από οτιδήποτε μπορεί να αντιμετωπίσει τα μαθηματικά μέχρι τον λογισμό.Υπάρχουν πολλά φανταστικά προβλήματα στην θεωρία της υπολογιστικής πολυπλοκότητας που θα απαιτούσαν ένα σχεδόν εύκαμπτο χρονικό διάστημα για την επίλυση. Αλγοριθμική πολυπλοκότητα και οι σχετικές έννοιες αναπτύχθηκαν στη δεκαετία του 1960 από δεκάδες ερευνητές.Οι Andrey Kolmogorov, Ray Solomonoff και Gregory Chaitin συνέβαλαν σημαντικά στα τέλη της δεκαετίας του '60 με αλγοριθμική θεωρία πληροφοριών.Η αρχή του ελάχιστου μήκους μηνυμάτων, που σχετίζεται στενά με την αλγοριθμική πολυπλοκότητα, παρέχει μεγάλο μέρος της θεμελίωσης στατιστικών και επαγωγικών συμπερασμάτων και μηχανικής μάθησης.