Ποια είναι η θεωρία υπολογιστικής πολυπλοκότητας;

Η θεωρία υπολογιστικής πολυπλοκότητας είναι ένας τομέας μαθηματικών και επιστήμης των υπολογιστών που ασχολείται με τους πόρους που απαιτούνται για την επίλυση προβλημάτων σε ένα σύστημα υπολογιστών.Ορισμένες τεχνικές είναι διαθέσιμες για τον προσδιορισμό των απαιτήσεων πόρων ενός προβλήματος.Ορισμένα προβλήματα ενδέχεται να μην είναι εφικτά στα υπάρχοντα συστήματα υπολογιστών λόγω των απαιτήσεων των πόρων τους.Οι ερευνητές ταξινομούν προβλήματα με δυσκολία και μπορούν να διαιρέσουν τους υπολογισμούς σε προβλήματα πολυώνυμου (P) έναντι μη τελικών πολυωνυμικών (NP).

Η επίλυση ενός υπολογισμού απαιτεί πόρους όπως ο χρόνος, ο χώρος αποθήκευσης και το υλικό.Ένα σύστημα υπολογιστών μπορεί να έχει περιορισμούς που καθιστούν ένα πρόβλημα λειτουργικά αδύνατο να επιλυθεί επειδή δεν διαθέτει τους διαθέσιμους πόρους.Καθώς βελτιώνεται η τεχνολογία των υπολογιστών, ένα προηγουμένως ασταθές πρόβλημα μπορεί να γίνει επίλυση με τη βοήθεια της νέας τεχνολογίας και της έρευνας στον τομέα της θεωρίας της υπολογιστικής πολυπλοκότητας.Η λύση ενός προβλήματος δεν καθορίζεται απαραιτήτως από την πολυπλοκότητά του, αλλά από τους αλγόριθμους που χρησιμοποιούνται για την επίλυσή του.

Στην θεωρία υπολογιστικής πολυπλοκότητας, ένα πρόβλημα P είναι αυτό που μπορεί να επιλυθεί σε πολυωνυμικό χρόνο με έναν απλό αλγόριθμο.Μπορεί να απαιτεί ουσιαστικούς πόρους, αλλά είναι τόσο διαλυτή και ελεγχόμενη από τον υπολογιστή.Τέτοια προβλήματα θα μπορούσαν να θεωρηθούν ως γρήγορα επιλύονται, εφόσον ένας υπολογιστής έχει τους διαθέσιμους πόρους για να χειριστεί τους απαραίτητους υπολογισμούς. Τα προβλήματα NP είναι πιο περίπλοκα.Δεν είναι δυνατόν να εφαρμοστεί ένας μόνο αλγόριθμος και ίσως χρειαστεί να χρησιμοποιηθούν πιο προηγμένες επιλογές, όπως παράλληλες μηχανές Turing που μπορούν να διερευνήσουν διάφορες επιλογές.Το πρόβλημα μπορεί να είναι επιλύεται με αυτόν τον τρόπο, αλλά θα χρειαστεί σημαντικά περισσότερους πόρους.Τέτοια προβλήματα μπορεί να είναι ευκολότερα για τους χειριστές των ανθρώπων που είναι ικανοί για προηγμένη λογική σκέψη, επειδή το σημείο ανατροπής είναι συχνά ένα από τη λογική και όχι τη δυσκολία υπολογισμού.Το πρόβλημα του πωλητή ταξιδιού, στο οποίο ο στόχος είναι να βρεθεί η πιο αποτελεσματική διαδρομή μεταξύ μιας σειράς πόλεων κατά μήκος μιας διαδρομής, είναι ένα κλασικό παράδειγμα ενός προβλήματος NP στην υπολογιστική θεωρία.Μπορεί να είναι ένα πολύπλοκο έργο και τα προβλήματα μπορεί να μετατοπιστούν πέρα και πίσω σε όλο το χάσμα.Ένα μικρό σύνολο υπολογιστικών προβλημάτων δεν ταιριάζει τακτοποιημένα σε καμία από τις δύο κατηγορίες και μερικές φορές ταξινομούνται ως ούτε για να αντικατοπτρίζουν αυτό.Μπορεί τελικά να είναι δυνατή η ανάπτυξη ενός αλγορίθμου για την επίλυση ενός προβλήματος NP και σε ορισμένες περιπτώσεις μπορεί να ισχύει για άλλα προβλήματα που έχουν παρόμοια δομή.Σε άλλες, ωστόσο, μπορεί να είναι συγκεκριμένο για το πρόβλημα.Η διαδικασία διερεύνησης τέτοιων προγραμμάτων και αναπτυσσόμενων προσεγγίσεων για την επίλυσή τους είναι ένας σημαντικός τομέας μαθηματικών και επιστήμης των υπολογιστών που συμβάλλει στην ανάπτυξη προηγμένων συστημάτων υπολογιστών υψηλής ισχύος.