The first natural problem proven to be NP-complete was the Boolean satisfiability problem, also known as SAT. As noted above, this is the Cook–Levin theorem; its proof that satisfiability is NP-complete contains technical details about Turing machines as they relate to the definition of NP. However, after this problem was proved to be NP-complete, proof by reduction provided a simpler way to show that many other problems are also NP-complete, including the game Sudoku discussed earlier. In this case, the proof shows that a solution of Sudoku in polynomial time could also be used to complete Latin squares in polynomial time. This in turn gives a solution to the problem of partitioning tri-partite graphs into triangles, which could then be used to find solutions for the special case of SAT known as 3-SAT, which then provides a solution for general Boolean satisfiability. So a polynomial-time solution to Sudoku leads, by a series of mechanical transformations, to a polynomial time solution of satisfiability, which in turn can be used to solve any other NP-problem in polynomial time. Using transformations like this, a vast class of seemingly unrelated problems are all reducible to one another, and are in a sense "the same problem".
the first natural problem proven to be np-complete was the boolean satisfiability problem also known as sat as noted above this is the cook–levin theorem; its proof that satisfiability is np-complete contains technical details about turing machines as they relate to the definition of np however after this problem was proved to be np-complete proof by reduction provided a simpler way to show that many other problems are also np-complete including the game sudoku discussed earlier in this case the proof shows that a solution of sudoku in polynomial time could also be used to complete latin squares in polynomial time this in turn gives a solution to the problem of partitioning tri-partite graphs into triangles which could then be used to find solutions for the special case of sat known as 3-sat which then provides a solution for general boolean satisfiability so a polynomial-time solution to sudoku leads by a series of mechanical transformations to a polynomial time solution of satisfiability which in turn can be used to solve any other np-problem in polynomial time using transformations like this a vast class of seemingly unrelated problems are all reducible to one another and are in a sense "the same problem"