chap limits to computation lar computer nor does anybody in the world know of any other polynomial time algorithm to solve traveling salesman on regular computerdespite the fact that the problem has been studied extensively by many computer scientists for many years it turns out that there is large collection of problems with this propertywe know efficient non-deterministic algorithmsbut we do not know if there are efficient deterministic algorithms at the same timewe have not been able to prove that any of these problems do not have efficient deterministic algorithms this class of problems is called -complete what is truly strange and fascinating about -complete problems is that if anybody ever finds the solution to any one of them that runs in polynomial time on regular computerthen by series of reductionsevery other problem that is in can also be solved in polynomial time on regular computerdefine problem to be -hard if any problem in can be reduced to in polynomial time thusx is as hard as any problem in problem is defined to be -complete if is in pand is -hard the requirement that problem be -hard might seem to be impossiblebut in fact there are hundreds of such problemsincluding traveling salesman another such problem is called -clique -clique inputan arbitrary undirected graph and an integer outputyes if there is complete subgraph of at least verticesand no otherwise nobody knows whether there is polynomial time solution for -cliquebut if such an algorithm is found for -clique or for traveling salesmanthen that solution can be modified to solve the otheror any other problem in pin polynomial time the primary theoretical advantage of knowing that problem is -complete is that it can be used to show that another problem is -complete this is done by finding polynomial time reduction of to because we already know that all problems in can be reduced to in polynomial time (by the definition of -complete)we now know that all problems can be reduced to as well by the simple algorithm of reducing to and then from there reducing to