decision problem
A decision problem is a question whose only allowed answers are yes or no. "Is 91 a prime number?" No. "Does this list contain the value 7?" Yes or no. "Can these meetings all be scheduled without overlap?" Yes or no. Every instance gets exactly one of two verdicts. Decision problems are the simplest kind of computational problem, which is precisely why theorists love them: stripping the answer down to one bit makes it easier to compare how hard different problems are.
Formally, a decision problem partitions all legal inputs into two groups: the yes-instances (where the answer is yes) and the no-instances. Solving it means correctly stamping each input with its verdict. For example, the decision problem PRIME takes a whole number and answers yes exactly when it is prime, so 7 and 13 are yes-instances while 8 and 91 are no-instances. Many richer problems have a natural decision version: instead of "what is the shortest route?" (an optimization problem) you ask "is there a route shorter than 100 km?" — and the answer is just yes or no.
Why bother shrinking everything to yes/no? Because it gives a clean, uniform way to measure difficulty, which is the whole foundation of complexity theory and the famous classes P and NP. It also turns out you usually lose nothing: if you can answer the decision question "is there a route shorter than k?" quickly for every k, you can pin down the true shortest length by asking a handful of such questions. So decision problems are not a toy restriction — they are a deliberate lens that keeps the theory sharp while still reaching the problems we actually care about.
Decision problem REACHABLE: given a map and two towns, is there any route from the first to the second? Answer for every instance is exactly yes or no, never a number or a route.
One bit of output — the defining feature of a decision problem.
A decision problem only asks whether an answer exists, not what it is. "Is there a route shorter than 100 km?" can be yes without telling you the route — finding the route is a search or optimization problem.