Added to Favorites

Computing Dictionary

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)

Encyclopedia Britannica

Encyclopedia

**decision problem**

for a class of questions in mathematics and formal logic, the problem of finding, after choosing any question of the class, an algorithm or repetitive procedure that will yield a definite answer, "yes" or "no," to that question. The method consists of performing successively a finite number of steps determined by preassigned rules. In particular, the term is used for such procedures for finding whether-in a particular logistic system, logical calculus, or formal mathematical system-some given "well-formed formula" (generated in accordance with established formation rules) is or is not provable as a theorem of the system

Learn more about decision problem with a free trial on Britannica.com.

Encyclopedia Britannica, 2008. Encyclopedia Britannica Online.

Cite This Source

Cite This Source

Related Searches

Nearby Words

Copyright © 2014 Dictionary.com, LLC. All rights reserved.