Technically, a decision problem doesn’t return a solution; instead it returns either “yes” to indicate there is a solution or “no” to indicate no solutions. However, as a practical matter, decision problems are solved by looking for a solution, so returning the solution found instead of “yes” isn’t that much of a change and will be much more useful.
On the other hand, it may require extra work to solve a problem to determine of a problem can be solved. For example, the game of nim consists of some number of piles, each pile containing some number of beans. Two players alternate moves by selecting a pile and removing beans from the pile. The person making the last move wins. For a given configuration of bean piles, can the player who moves first win?
One way to answer the question is to keep playing games from the given configuration until the first player wins, or until all possible games have been played. However, there’s a simple mathematical analysis that can be preformed on the initial configuration that determines if, but not how, the first player can win.
This page last modified on 24 January 2006.