166 Are the Androids Dreaming Yet? | | | —— Piri ) ia : | j Maze clue which one will be better. Beware the confusing naming system, ‘N’ stands for nondeterministic in this case, whereas in normal complexity classes ‘n’ stands for number. Sorry. That’s just the way it is. Let me give you an example of one of these NP problems. Let us assume we have one of those complicated recipes from the latest celebrity chef cookbook. If all the ingredients can be bought from one store, making the dish is straightforward, but if they come from different stores, you will have your work cut out. What is the best order to visit them? With 2 shops, it’s trivial. Either order will do. With 3 it is a little harder and with 4 there is quite a bit of choice. This is known as the ‘traveling salesman’ problem because the original formulation described a salesman wishing to find the shortest route between all the cities in which he had customers. The complexity of this problem rises much faster than the Rice and Chess Board problem. Try it for yourself. It doesn’t matter if you imagine you are visiting customers or shops. I have given you a grid to count off distances. Try to solve a problem for 3 cities, 5 and 10. What is the shortest path allowing you to visit each place? HOUSE_OVERSIGHT_015856