there is practical advantage to knowing that problem is -complete it relates to knowing that if polynomial time solution can be found for any problem that is -completethen polynomial solution can be found for all such problems the implication is that because no one has yet found such solutionit must be difficult or impossible to doand effort to find polynomial time solution for one -complete problem can be considered to have been expended for all -complete problems how is -completeness of practical significance for typical programmerswellif your boss demands that you provide fast algorithm to solve problemshe will not be happy if you come back saying that the best you could do was an exponential time algorithm butif you can prove that the problem is pcompletewhile she still won' be happyat least she should not be mad at youby showing that her problem is -completeyou are in effect saying that the most brilliant computer scientists for the last years have been trying and failing to find polynomial time algorithm for her problem problems that are solvable in polynomial time on regular computer are said to be in class clearlyall problems in are solvable in polynomial time on non-deterministic computer simply by neglecting to use the non-deterministic capability some problems in are -complete we can consider all problems solvable in exponential time or better as an even bigger class of problems because all problems solvable in polynomial time are solvable in exponential time thuswe can view the world of exponential-time-or-better problems in terms of figure the most important unanswered question in theoretical computer science is whether if they are equalthen there is polynomial time algorithm for traveling salesman and all related problems because traveling salesman is known to be -completeif polynomial time algorithm were to be found for this problemthen all problems in would also be solvable in polynomial time converselyif we were able to prove that traveling salesman has an exponential time lower boundthen we would know that -completeness proofs to start the process of being able to prove problems are -completewe need to prove just one problem is -complete after thatto show that any problem is -hardwe just need to reduce to when doing -completeness proofsit is very important not to get this reduction backwardsif we reduce candidate problem to known hard problem hthis means that we use as step to solving all that means is that we have found (knownhard way to solve