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)