decision problem

(redirected from Decidable problem)

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.
References in periodicals archive ?
Satisfiability (validity) is a decidable problem for a logic if there exists a decision procedure for the satisfiability (validity) of every formula of the logic.
However, the minimal description length--the complexity--of any given algorithm or program turns out not to be calculable; that is, on the terms of computational complexity theory noted above, it is not a decidable problem (Chaitin [1974], theorem 2).
Partially decidable problems and any other problems that are not decidable are referred to as undecidable.