decision problem

theory A problem with a yes/no answer. Determining whether

some potential solution to a question is actually a solution

or not. E.g. "Is 43669" a prime number?". This is in

contrast to a "search problem" which must find a solution

from scratch, e.g. "What is the millionth prime number?".

See decidability.

(1996-05-03)