Complexity and Tractability
12.6. Other intractable problems

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)