graph algorithms figure hamiltonian cycle problem transformed to traveling salesman problem problems are considered before the problem that actually provides the reduction as we are only interested in the general ideaswe will not show any more transformationsthe interested reader can consult the references the alert reader may be wondering how the first np-complete problem was actually proven to be np-complete since proving that problem is np-complete requires transforming it from another np-complete problemthere must be some np-complete problem for which this strategy will not work the first problem that was proven to be np-complete was the satisfiability problem the satisfiability problem takes as input boolean expression and asks whether the expression has an assignment to the variables that gives value of true satisfiability is certainly in npsince it is easy to evaluate boolean expression and check whether the result is true in cook showed that satisfiability was np-complete by directly proving that all problems that are in np could be transformed to satisfiability to do thishe used the one known fact about every problem in npevery problem in np can be solved in polynomial time by nondeterministic computer the formal model for computer is known as turing machine cook showed how the actions of this machine could be simulated by an extremely complicated and longbut still polynomialboolean formula this boolean formula would be true if and only if the program which was being run by the turing machine produced "yesanswer for its input once satisfiability was shown to be np-completea host of new np-complete problemsincluding some of the most classic problemswere also shown to be np-complete in addition to the satisfiabilityhamiltonian circuittraveling salesmanand longestpath problemswhich we have already examinedsome of the more well-known npcomplete problems which we have not discussed are bin packingknapsackgraph coloringand clique the list is quite extensive and includes problems from operating systems (scheduling and security)database systemsoperations researchlogicand especially graph theory