## Thursday, October 07, 2004

### NP-Completeness for a 9-Year Old

My nine-year old daughter had a homework problem with the following diagram.

She had no problem solving questions like: Beginning and ending at the entrance, describe the shortest route you can take that will allow you to see 4 different kinds of animals.

"You're doing computer science," I said.

"I don't see any computers," she responded.

"Computer science is problem solving like finding the shortest path."

"Then computer science is pretty easy."

"OK, is there a way to visit every animal exactly once?"

She found this question much more challenging.

#### 5 comments:

1. Do you mean "shortest path that visits each animal exactly
once"? Otherwise it really isn't very hard...

2. You didn't specify if you could traverse the same path more than once.

3. Traversing this Zoo is very complex!

4. is the problem of shortest path using eucliadian distance is not polynomial? roads on the map you poiuned are almost straight so the problem must be close to euclidian

5. I'm not sure if Euclidean hamiltonian path is NP-hard, but Euclidean TSP remains NP-hard and has a polynomial time approximation scheme. See http://citeseer.ist.psu.edu/arora96polynomial.html