sec hard problems figure an illustration of the traveling salesman problem five vertices are shownwith edges between each pair of cities the problem is to visit all of the cities exactly oncereturning to the start citywith the least total cost route would be abdceawith cost the best route for this particular graph would be abedcawith cost we cannot solve this problem in polynomial time with guess-and-test nondeterministic computer the problem is thatgiven candidate cyclewhile we can quickly check that the answer is indeed cycle of the appropriate formand while we can quickly calculate the length of the cyclewe have no easy way of knowing if it is in fact the shortest such cycle howeverwe can solve variant of this problem cast in the form of decision problem decision problem is simply one whose answer is either yes or no the decision problem form of traveling salesman is as followstraveling salesman ( inputa completedirected graph with positive distances assigned to each edge in the graphand an integer outputyes if there is simple cycle with total distance < containing every vertex in gand no otherwise we can solve this version of the problem in polynomial time with non-deterministic computer the non-deterministic algorithm simply checks all of the possible subsets of edges in the graphin parallel if any subset of the edges is an appropriate cycle of total length less than or equal to kthe answer is yesotherwise the answer is no note that it is only necessary that some subset meet the requirementit does not matter how many subsets fail checking particular subset is done in polynomial time by adding the distances of the edges and verifying that the edges form cycle that visits each vertex exactly once thusthe checking algorithm runs in polynomial time unfortunatelythere are |esubsets to checkso this algorithm cannot be converted to polynomial time algorithm on regu