The problem \(3\text{-}\sc{SAT}\) was shown to be \(\textbf{NP}\)-complete in Cook’s original paper (Cook 1971).[19] The other examples just cited are taken from a list of 21 problems (most of which had previously been identified in other contexts) which were shown by Karp (1972) to be \(\textbf{NP}\)-complete. The reductions required to show the completeness of these problems typically require the construction of what has come to be known as a gadget – i.e. a constituent of an instance of one problem which can be used to simulate a constituent of an instance of a different problem.  For instance, in order to see how \(3\text{-}\sc{SAT}\) may be reduced to \(\sc{INDEPENDENT}\ \sc{SET}\), first observe that a \(3\text{-}\sc{CNF}\) formula has the form