< 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)