Nótese que este diagrama puede resultar engañoso al llevarnos a pensar que muestra una descripción de la relación matemática entre esos problemas, ya que existe una relación de reducción de tiempo polinómico entre dos problemas NP-completos cualesquiera; pero esto indica que demostrar estas reducciones de tiempo polinómicas ha sido más fácil.