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