Θεωρία πολυπλοκότητας: Διαφορά μεταξύ των αναθεωρήσεων

Η θεωρία πολυπλοκότητας ταξινομεί τα προβλήματα σε κλάσεις(σύνολα) ισοδυναμίας που ορίζουν ότι τα προβλήματα στην ίδια κλάση έχουν την ίδια δυσκολία.Ιδιαιτέρου ενδιαφέροντος στο πλαίσιο αυτό ειναι οι κλάσεις P(Deterministic Polynomial Time) και NP(Non Deterministic Polynomial Time).Γενικά θα μπορούσαμε να πούμε ότι η κλάση PNP περιλαμβάνει τα περισσότερα προβλήματα της NPP.Θα προχωρήσουμε σε πιο τυπικούς ορισμούς οι οποιοι επαλυθεύουν τη διαίσθηση ότι P⊆NP.Θα πρέπει να τονίσουμε ότι οι κλάσεις P και NP ορίζονται ως προς '''προβλήματα απόφασης''', δηλαδή προβλήματα στα οποία καλούμαστε να απαντήσουμε μια συγκεκριμένη ερώτηση με ΝΑΙ ή ΟΧΙ.