a decision problem

A decision problem is any problem whose answer is just yes or no, never a number, a list, or a picture, only one of two verdicts. Is this number prime? Does this graph contain a triangle? Will this program ever stop? Each is a decision problem, and stripping problems down to a single yes-or-no answer is what makes them clean enough for a uniform theory.

Formally, a decision problem is a function from inputs to {yes, no}. Because we encode each input as a string and gather the yes-inputs into a set, every decision problem corresponds exactly to a language: the language of all strings whose answer is yes. Solving the decision problem means, for any input string, correctly reporting yes (the string is in the language) or no (it is not). This is why decision problems and languages are two views of the same thing, and why the membership question is the universal form of a decision problem.

Why narrow our attention to yes/no problems? Because this restriction loses almost nothing important while making the theory tractable: most optimization and search problems have a decision version of nearly equal difficulty (instead of find the largest clique, ask is there a clique of size at least k?). It also lets us classify difficulty cleanly. A decision problem is called decidable if some algorithm always halts with the right yes/no answer, and undecidable if no such algorithm can exist for all inputs (the halting problem is the famous undecidable example). And among decidable problems, complexity classes like P and NP further sort them by how much time or memory is needed.