Complexity and Tractability
12.8. Other intractable problems
There are thousands of problems like the TSP for which no tractable solution is known. A few examples are:
- 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
