More material on the many intractable problems that exist is yet to be written, but in the meantime, here are some alternatives to the TSP problem that can be used to explore intractability if you have students who can work on this independently.
Complexity and Tractability
12.6. Other intractable problems
Under construction Teacher Note
There are thousands of problems like the TSP for which no tractable solution is known. Extra sections will eventually be added here to introduce some of them, but in the meantime, if you are keen you might like to explore some of these problems:
- Map and graph colouring (these can be reduced to a timetabling problem and vice versa, showing how NP-complete problems can relate to each other)
- The knapsack problem
- Hamiltonian paths (no tractable solution for this is known, yet the very similar Eulerian path, which is often presented as the seven bridges problem, has an easy tractable solution)
- Steiner trees
- Dominating sets
- Longest path (this is interesting because finding the longest path is intractable, yet finding the shortest path is tractable - the shortest path is calculated when a GPS device works out the shortest route to a destination. Also, a Hamiltonian problem can be reduced easily to longest path, showing the concept of reduction when one NP-complete problem is used to solve another). Here's a song about it!
- The Battleship problem
