decision problem
decision problem A computational task that for each possible input requires “true” or “false” to be output, depending on whether the input possesses a certain property. An algorithm that produces the correct decision in each case is called a decision procedure for that problem. If a decision procedure exists then the problem is said to be (algorithmically) solvable, while an (algorithmically) unsolvable problem is one for which no decision procedure exists. An example is logical validity, the inputs being logical expressions, with the output “true” for valid expressions and “false” for others. This problem is solvable for propositional logic (the construction of truth tables being a decision procedure) but not for predicate logic (by Church's theorem of 1936). Solvable problems can be further classified according to the efficiency of decision procedures existing for them (see P=NP question).
Some unsolvable problems possess a semidecision procedure, i.e. an algorithm that correctly outputs “true” but fails to terminate in cases where “false” should be output. This is the same as saying that the inputs requiring the output “true” form a set that is recursively enumerable (but need not be recursive). Alternatively one can say that the problem corresponds to a predicate that is semidecidable (but need not be decidable).
Some unsolvable problems possess a semidecision procedure, i.e. an algorithm that correctly outputs “true” but fails to terminate in cases where “false” should be output. This is the same as saying that the inputs requiring the output “true” form a set that is recursively enumerable (but need not be recursive). Alternatively one can say that the problem corresponds to a predicate that is semidecidable (but need not be decidable).
More From encyclopedia.com
Decision Making , Decision making, also referred to as problem solving, is the process of recognizing a problem or opportunity and finding a solution to it. Decisions… Herbert Alexander Simon , Simon, Herbert Alexander
SIMON, HERBERT ALEXANDER
Simon’s lifelong passion was the study of decision-making and problem-solving. He examined these pr… Decision Support Systems , Broadly speaking, decision support systems are a set of manual or computer-based tools that assist in some decision-making activity. In today's busin… Procedure , procedure •badger, cadger •Alger, neuralgia •ganja, grandeur, phalanger •charger, enlarger, maharaja, raja •slàinte • turbocharger •dredger, edger, h… Decision , decision •abrasion, Australasian, equation, Eurasian, evasion, invasion, occasion, persuasion, pervasion, suasion, Vespasian •adhesion, cohesion, Fri… SPARC , SPARC Trademark; Acronym for scalable processor architecture. Sun Microsystems' RISC architecture intended for multiple implementations with differin…
You Might Also Like
NEARBY TERMS
decision problem