La herramienta principal para lograr estas clasificaciones es el concepto de reducibilidad: Un problema formula_1 se reduce al problema formula_2 si bajo la suposición de que se sabe resolver el problema formula_2 es posible resolver al problema formula_1; esto se denota por formula_5, e informalmente significa que el problema formula_1 "no es más difícil de resolver" que el problema formula_2.