Difficult Problems
There are a variety of kinds of problems that computers “cannot” perform
- Unsolvable problems cannot be computed … solving them is logically inconsistent
- Some problems cannot be solved because the inputs cannot be known … predicting today’s close of the Amazon.Com stock price
- Some problems could be solved in principle, but it would take so long and take so many resources that it is impractical … simulating the positions of the stars in the Milky Way galaxy over a million years
- Intractable problems could be solved if you could guess effectively, but with known methods, they are impractical
The Knapsack problem is an example of an intractable problem