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

Μια από τις θεμελιώδεις κλάσεις πολυπλοκότητας είναι η P  ή PTIME  που περιλαμβάνει όλα τα προβλήματα απόφασης, εκείνα που μπορούν να λυθούν σε πολυωνυμικό χρόνο χρησιμοποιώντας μια Ντετερμινιστική Μηχανή Turing.
Η μηχανή Turing είναι ένα υπολογιστικό μοντέλο το οποίο μπορεί να προσομοιώσει οποιαδήποτε αλγοριθμική λογική. Έτσι σε μια μηχανή Turing για κάθε δοθείσα διάταξη( περιγράφεται από την παρούσα κατάσταση και από το σύμβολο εισόδου) υπάρχει τουλάχιστον μία πιθανή μετάβαση (περιγράφεται από την επόμενη κατάσταση, το σύμβολο εξόδου, και την κίνηση πάνω στην ταινία). Αυτό σημαίνει ότι για κάθε δοθείσα είσοδο θα έχουμε μια τουλάχιστον έξοδο.

Σε μια Μη- Ντετερμινιστική μηχανή Turing για κάθε δοθείσα διάταξη υπάρχει παραπάνω από μία πιθανή μετάβαση. Αυτό σημαίνει ότι για κάθε δοθείσα είσοδο σε μια μη- ντετερμινιστική μηχανή Turing μπορεί να υπάρχουν περισσότερες από μία πιθανές εξόδους. Μια τέτοια μηχανή Turing αποδέχεται ένα στιγμιότυπο του προβλήματος εάν τουλάχιστον μια από τις πιθανές εξόδους είναι «Yes». 

Όλα τα προβλήματα που λύνονται σε πολυωνυμικό χρόνο από μια μη–ντετερμινιστική μηχανή Turing απαρτίζουν την κλάση NP . Ωστόσο δεν θα πρέπει να ξεχνάμε, ειδικά προβλήματα που σχηματίζουν την κλάση NP-Complete (NP-Πλήρη). Αν ένα πρόβλημα NP-Complete  λυθεί σε πολυωνυμικό χρόνο από μια ντετερμινιστική μηχανή Turing τότε μπορεί να λυθεί οποιοδήποτε πρόβλημα στην NP.
Δοθέντος ενός αλγόριθμου για ένα NP-Complete πρόβλημα, θεωρώντας ότι, P≠ NP το ερώτημα είναι πόσο καλά μπορούμε να προσεγγίσουμε την βέλτιστη λύση του προβλήματος.