problemp can be reduced to as followsprovide mapping so that any instance of can be transformed to an instance of solve and then map the answer back to the original as an examplenumbers are entered into pocket calculator in decimal the decimal numbers are converted to binaryand all calculations are performed in binary then the final answer is converted back to decimal for display for to be polynomially reducible to all the work associated with the transformations must be performed in polynomial time the reason that np-complete problems are the hardest np problems is that problem that is np-complete can essentially be used as subroutine for any problem in npwith only polynomial amount of overhead thusif any np-complete problem has polynomial-time solutionthen every problem in np must have polynomial-time solution this makes the np-complete problems the hardest of all np problems suppose we have an np-complete problemp suppose is known to be in np suppose further that polynomially reduces to so that we can solve by using with only polynomial time penalty since is np-completeevery problem in np polynomially reduces to by applying the closure property of polynomialswe see that every problem in np is polynomially reducible to we reduce the problem to and then reduce to thusp is np-complete as an examplesuppose that we already know that the hamiltonian cycle problem is np-complete the traveling salesman problem is as follows traveling salesman problem given complete graphg (ve)with edge costsand an integer kis there simple cycle that visits all vertices and has total cost <kthe problem is different from the hamiltonian cycle problembecause all | |(| |- )/ edges are present and the graph is weighted this problem has many important applications for instanceprinted circuit boards need to have holes punched so that chipsresistorsand other electronic components can be placed this is done mechanically punching the hole is quick operationthe time-consuming step is positioning the hole puncher the time required for positioning depends on the distance traveled from hole to hole since we would like to punch every hole (and then return to the start for the next board)and minimize the total amount of time spent travelingwhat we have is traveling salesman problem the traveling salesman problem is np-complete it is easy to see that solution can be checked in polynomial timeso it is certainly in np to show that it is np-completewe polynomially reduce the hamiltonian cycle problem to it to do this we construct new graphgghas the same vertices as for geach edge (vwhas weight of if (vwgand otherwise we choose |vsee figure it is easy to verify that has hamiltonian cycle if and only if ghas traveling salesman tour of total weight |vthere is now long list of problems known to be np-complete to prove that some new problem is np-completeit must be shown to be in npand then an appropriate np-complete problem must be transformed into it although the transformation to traveling salesman problem was rather straightforwardmost transformations are actually quite involved and require some tricky constructions generallyseveral different np-complete