(theory)A problem with a yes/no answer. Determining whethersome potential solution to a question is actually a solutionor not. E.g. "Is 43669" a prime number?". This is incontrast to a "search problem" which must find a solutionfrom scratch, e.g. "What is the millionth prime number?".