Mientras que la pertenencia del problema SAT o de satisfacibilidad booleana a la clase de los NP-completos fue demostrada utilizando mecanismos particulares, las pertenencias de los 21 problemas siguientes fueron demostradas mediante reducciones polinomiales.