Η τεχνική για να αποδείξουμε πως ένα πρόβλημα είναι μη αποφασίσιμο είναι να το αναγάγουμε σε ένα γνωστό μη αποφασίσιμο πρόβλημα. Έτσι στα πλαίσια της πολυπλοκότητας η αναγωγή ενός προβλήματος σε ένα άλλο γνωστής πολυπλοκότητας επίλυσης μας επιτρέπει να προσδιορίσουμε την πολυπλοκότητα του. 

Η τεχνική αυτή, της Αναγωγής, μας επιτρέπει να προσδιορίσουμε για κάποιες κλάσεις πολυπλοκότητας όπως οι Ρ και ΝΡ, τα πλήρη προβλήματα στα οποία ανάγονται όλα τα άλλα.
Γενικά ένα πρόβλημα ορίζεται με ένα πεπερασμένο αριθμό παραμέτρων και ένα ερώτημα. Το ερώτημα περιλαμβάνει ένα σημαντικό πλήθος λεκτικής πληροφορίας και ήδη γνωστής σημασιολογίας ώστε να αποφεύγετε ο ορισμός των πάντων από την αρχή. Οι παράμετροι όταν παίρνουν συγκεκριμένες τιμές, ορίζουν ένα στιγμιότυπο του προβλήματος.
Οι κύριες κατηγορίες προβλημάτων είναι :
1. Προβλήματα απόφασης, είναι αυτά που απαιτούν μια απάντηση ΝΑΙ/ ΟΧΙ.
2. Προβλήματα αναζήτησης, η απάντηση τους είναι μια δομή που πληρεί κάποιες απαιτήσεις. 
3. Προβλήματα βελτιστοποίησης, εκτός του ότι η απάντηση θα πρέπει να πληρεί κάποιες απαιτήσεις θα πρέπει ακόμα να βελτιστοποιεί μια αντικειμενική συνάρτηση.
4. Προβλήματα απαρίθμησης, η απάντηση είναι μια λίστα από όλες τις δομές που ικανοποιούν τις απαιτήσεις του προβλήματος.
5. Προβλήματα άθροισης, η απάντηση είναι ουσιαστικά το πλήθος των δομών που πληρούν τις απαιτήσεις του.

Τα γνωστότερα πλήρη προβλήματα ή αλλιώς NP-Complete Problems είναι:

1. Το πρόβλημα SAT (SATisfiability) 

2. Το πρόβλημα Hamilton Cycle

3. Το πρόβλημα Hamilton Path

4. Το πρόβλημα Traveling Salesman Problem

5. Το πρόβλημα Independent Set

6. Το πρόβλημα Clique

7. Το πρόβλημα Vertex Cover

8. Το πρόβλημα Edge Cover

9. Το πρόβλημα Maximum Cut

10. Το πρόβλημα Graph 3-Coloring

11. Το πρόβλημα Partition

12. Το πρόβλημα 2-Machine SCheduling 

13. Το πρόβλημα Bin Packing

14. Το πρόβλημα Knapsack

15. Το πρόβλημα Tripartime Matching

16. Το πρόβλημα Set Cover

17. Το πρόβλημα Exact Cover

Η Αναγωγή

Αν μια κλάση προβλημάτων Κ και ένας τύπος αναγωγής t, θα λέμε ότι ένα πρόβλημα Α είναι πλήρες για την κλάση Κ ή Κ-Πλήρες εάν ισχύουν τα παρακάτω:

  • Α∈ K  και
  • ∀ Β∈ Κ είναι Β ≤t Α

Αν στο πρόβλημα Α ισχύει μόνο η δεύτερη σχέση τότε το πρόβλημα θα είναι Κ-Σκληρό. Γενικά η δεύτερη σχέση μας λέει ότι το πρόβλημα Α είναι το δυσκολότερο στην κλάση Κ. Αυτό σημαίνει πρακτικά ότι ανάγεται σε αυτό ένα Κ-Πλήρες πρόβλημα με δεδομένου ότι στο Κ-Πλήρες ανάγονται όλα τα προβλήματα της κλάσης Κ. Για παράδειγμα αν ένα πρόβλημα απόφασης είναι Κ-Πλήρες τότε το αντίστοιχο πρόβλημα σαν πρόβλημα βελτιστοποίησης θα είναι Κ-Σκληρό.

Έτσι, εξειδικεύοντας την έννοια της πληρότητας για τις κλάσεις Ρ, ΝΡ και ΕΧΡ, θα λέμε ότι η
Ρ-πληρότητα ορίζεται από αναγωγές λογαριθμικού χώρου, ενώ η ΝΡ-πληρότητα όπως και η ΕΧΡ από αναγωγές πολυωνυμικού χώρου.

Ένα πρόβλημα απόφασης Α καλείται ΝΡ-Πλήρες εάν
  • Α∈ ΝΡ  και
  • ∀ Β∈ ΝΡ υπάρχει πολυωνυμική αναγωγή Β ≤t Α
Με άλλα λόγια, 
Έαν Α είναι ΝΡ-Πλήρες και υπάρχει πολυωνυμική αναγωγή του Α ≤fΒ με Β∈ ΝΡ τότε και το Β είναι ΝΡ-Πλήρες.
Παρακάτω δίνουμε ένα απλό παράδειγμα για να δείξουμε το πως δουλεύουμε με την αναγωγή στην ΝΡ-πληρότητα.

Έστω το πρόβλημα : "Δεδομένου γράφου G(V,E) και ακεραίου k≥ 2, υπάρχει σύνολο ανεξαρτησίας τουλάχιστον k-κορυφών; " Να αποδειχθεί ότι το Σύνολο Ανεξαρτησίας (Independent Set) είναι ΝΡ-Πλήρες με αναγωγή στο Clique.

Απάντηση:
Έστω γράφος G(V,E) και ακέραιος k ≥2,  και μια υποθετική λύση δηλαδή G'(V',E') είναι κλίκα
με V'⊆ V. Τότε ένας "επαληθευτής" ελέγχει αν |V'| =k σε χρόνο O(v). Ακόμα ελέγχει ανά δύο τις κορυφές V'  αν συνδέονται με ακμή σε χρόνο το πολύ Ο(v^2). Και στις δύο αυτές περιπτώσεις ο χρόνος είναι πολυωνυμικός.

Ευθύ⋙
Αν το G είναι ένα "ΝΑΙ" στιγμιότυπο του  τότε το G έχει κλίκα με τουλάχιστον k-κορυφές κατά συνέπεια το G' (συμπλήρωμα του G) έχει σύνολο ανεξαρτησίας με τουλάχιστον k-κορυφές. Δηλαδή το G'  είναι ένα "ΝΑΙ" στιγμιότυπο του Συνόλου Ανεξαρτησίας.

Αντίστροφο⋘
Αν το G' είναι ένα "ΝΑΙ" στιγμιότυπο του Συνόλου Ανεξαρτησίας, τότε το G αποτελεί το "ΝΑΙ" στιγμιότυπο του Clique.

Συνεπώς το Σύνολο Ανεξαρτησίας ανάγεται πολυωνυμικά στο Clique.