chap limits to computation the theory of -completeness imagine magical computer that works by guessing the correct solution from among all of the possible solutions to problem another way to look at this is to imagine super parallel computer that could test all possible solutions simultaneously certainly this magical (or highly parallelcomputer can do anything normal computer can do it might also solve some problems more quickly than normal computer can consider some problem wheregiven guess for solutionchecking the solution to see if it is correct can be done in polynomial time even if the number of possible solutions is exponentialany given guess can be checked in polynomial time (equivalentlyall possible solutions are checked simultaneously in polynomial time)and thus the problem can be solved in polynomial time by our hypothetical magical computer another view of this concept is that if you cannot get the answer to problem in polynomial time by guessing the right answer and then checking itthen you cannot do it in polynomial time in any other way the idea of "guessingthe right answer to problem -or checking all possible solutions in parallel to determine which is correct -is called non-determinism an algorithm that works in this manner is called non-deterministic algorithmand any problem with an algorithm that runs on non-deterministic machine in polynomial time is given special nameit is said to be problem in thusproblems in are those problems that can be solved in polynomial time on non-deterministic machine not all problems requiring exponential time on regular computer are in for exampletowers of hanoi is not in pbecause it must print out ( moves for disks non-deterministic machine cannot "guessand print the correct answer in less time on the other handconsider what is commonly known as the traveling salesman problem traveling salesman ( inputa completedirected graph with positive distances assigned to each edge in the graph outputthe shortest simple cycle that includes every vertex figure illustrates this problem five vertices are shownwith edges and associated costs between each pair of edges (for simplicitywe assume that the cost is the same in both directionsthough this need not be the case if the salesman visits the cities in the order abcdeahe will travel total distance of better