# 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 , theorem 2).
Partially decidable problems and any other problems that are not decidable are referred to as undecidable.
Next, decidable problems and undecidable problems in PDAs and VPAs are explained.

Site: Follow: Share:
Open / Close