Reasoning foundations
Decision problem
A problem whose answer is one of a fixed set of outcomes, usually yes or no.
Definition
Decision problem
A decision problem asks whether an input has a stated property.
SAT asks whether a Boolean formula has a satisfying assignment. An implementation may also return evidence, but the main result remains a decision.
01
Example
Given a list of course requirements, does any valid schedule exist?
02
Important distinction
Finding the best schedule is an optimization problem, although repeated decision questions can sometimes solve it.
After reading this article, you should be able to
- Define Decision problem in the sense used on this site.
- Distinguish a decision problem from a search or optimization problem.