decision problem

Computing Dictionary

decision problem definition

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.
(1996-05-03)

The Free On-line Dictionary of Computing, © Denis Howe 2010 http://foldoc.org
Cite This Source
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
Copyright © 2014 Dictionary.com, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature