Así, el problema SAT se "redujo" polinomialmente a los problemas 0-1 INTEGER PROGRAMMING, CLIQUE y 3-SAT, y estos a su vez se redujeron a otros varios.