Ανάλογα με τον υπολογιστικό χρόνο επίλυσης, τα προβλήματα κατατάσσονται σε κλάσεις.

1. Η κλάση P

Είναι η κλάση πολυωνυμικoύ  χρόνου ( Polynomial ) και ταυτίζεται με τα προβλήματα που μπορούν να λυθούν αποδοτικά από μια υπολογιστική μηχανή. Σε αυτή την κλάση ανήκουν τα ευεπίλυτα προβλήματα για τα οποία υπάρχει πολυωνυμικός αλγόριθμος επίλυσης ή είναι «εύκολο» να βρούμε έναν.

2. Η κλάση NP (Nondeterministic Polynomial)

  Σε αυτή ανήκουν προβλήματα που απαιτούν εκθετικό χρόνο επίλυσης και δεν έχουμε καμία ένδειξη για ύπαρξη ενός πολυωνυμικού αλγορίθμου ικανού να δώσει λύση. Αυτό όμως που γνωρίζουμε είναι ότι για κάθε ΝΑΙ στιγμιότυπο, ενός προβλήματος απόφασης, επαληθεύεται σε πολυωνυμικό χρόνο αν η δοθείσα απάντηση είναι και η λύση του.
Στην κλάση NP κατατάσσονται και τα NP-Πλήρη(NP-Complete) προβλήματα. Δηλαδή τα προβλήματα εκείνα που οι υπάρχοντες αλγόριθμοι είναι  εκθετικού  χρόνου  και κάθε άλλο πρόβλημα που ανήκει στην NP ανάγεται πολυωνυμικά σα αυτά, δηλαδή μπορούν και σχηματίζουν μια σχέση ισοδυναμίας μεταξύ τους. Φυσικά όλα τα NP προβλήματα δεν είναι NP-Πλήρη.
Ακόμα μια αρνητική απάντηση σε ένα NP πρόβλημα δεν έχει απαραίτητα σύντομο επαληθευτή. Γι’ αυτό το λόγο τα συμπληρωματικά προβλήματα της NP κλάσης αποτελούν μια κλάση την co-NP «με το ίδιο σύνολο στιγμιότυπων αλλά με αντεστραμμένα τα ΝΑΙ και τα ΟΧΙ στιγμιότυπα μέσω της άρνησης της ερώτησης»
Tην σχέση των κλάσεων αυτών την απεικονίζουμε συνήθως με την παρακάτω αναπαράσταση


3.Η κλάση EXP (EXPonential)

Περιλαμβάνει προβλήματα που τόσο ο χρόνος επίλυσης τους όσο και ο χρόνος επαλήθευσης είναι εκθετικός. Δηλαδή πραγματικά δύσβατα προβλήματα.


Βέβαια όταν αναφερόμαστε σε NP-Πλήρη προβλήματα θα πρέπει να πούμε ότι θεωρούμε P≠NP  . Γιατί αν P=NP  τότε θα έπρεπε ένα Α NP-Πλήρες πρόβλημα να λύνεται σε πολυωνυμικό χρόνο (δηλαδή το A ανήκει στην Ρ  ) και ακόμα κάθε πρόβλημα Κ  που ανήκει στην NP θα ανάγεται πολυωνυμικά στο Α . Τότε εφόσον Α ανήκει στην Ρ και κάθε Κ ανήκει στην ΝΡ θα ανήκει επίσης στη Ρ .
  
Ακόμα  αν ένα πρόβλημα απόφασης είναι NP-Πλήρες  και υπάρχει η εκδοχή βελτιστοποίησης του, τότε το πρόβλημα βελτιστοποίησης θα λέμε ότι είναι NP-Σκληρό (NP-Hard).
Γενικά το ερώτημα αν  Ρ=ΝΡ ή P≠NP   παραμένει. Ωστόσο μετά από πολύχρονες αποτυχημένες προσπάθειες δεν έχει βρεθεί (ακόμα τουλάχιστον) πολυωνυμικός αλγόριθμος επίλυσης για NP-Πλήρη προβλήματα δίνοντας μας την πεποίθηση ότι το P≠NP  ισχύει. 

Στον παρακάτω πίνακα  παρουσιάζονται μερικά από τα δύσκολα και εύκολα προβλήματα  καθώς και οι αναγωγές μεταξύ των προβλημάτων απόφασης

Δύσκολα NP-Πλήρη προβλήματα
Εύκολα προβλήματα στο P
3SAT
Συντομότερη διαδρομή
TSP
Διμερής αντιστοίχιση
Μεγαλύτερη Διαδρομή
Ελάχιστη τομή
Knapsack
Independent Set σε δέντρα
Independent Set
Διαδρομή Euler
Διαδρομή Rudrata
2SAT
Node Cover

Clique




Αναγωγές  των προβλημάτων απόφασης
Πηγή: Προσεγγιστικοί αλγόριθμοι για τα προβλήματα Node Cover και Independent Set