In logic, a decision problem is determining whether or not there exists a decision procedure or algorithm for a class S of questions requiring a Boolean value (i.e., a ''true'' or ''false'', or ''yes'' or ''no''). These are also known as yes-or-no questions. For example, the decision problem for the class of questions "Does ''x'' divide ''y'' without remainder?" is ''decidable'' because there exists a mechanical procedure, namely long division, which allows us to determine for any ''x'' and any ''y'' whether the answer for "Does ''x'' divide ''y'' without remainder?" is ''yes'' or ''no''. Every decision problem is reducible to a computation problem in the following way. Every class of yes-or-no questions is reducible to the predicate form "Is true?". For example, the above example is reducible to "Is true?". This predicate form is reducible to the representing function So deciding whether is true is equivalent to computing the value for . ==Definition== A decision problem is a countable set ''S'' and a function_(mathematics) :. Let ''A'' be the preimage of ''f'' for 0. : The problem is called decidable if ''A'' is a recursive set. It is called partially decidable, solvable or provable if ''A'' is a recursively enumerable set. Otherwise, the problem is called undecidable. We can give an alternative definition in terms of computable functions: If ''f'' is a total function computable function, the problem is called computable. If ''f'' is only a partial function computable function, the problem is called partially computable. Otherwise, the problem is called uncomputable. ==Notes== It should be noted that a decision problem is always a set of related problems which is in some sense large enough. A single problem ''P'' is always trivially decidable by assigning the constant function ''f''(''P'')≡0 or ''f''(''P'')≡1 to it. Nearly every problem can be cast as a decision problem by using reduction (complexity)s, often with little effect on the amount of time or space needed to solve the problem. Many traditional hard problems have been cast as decision problems because this makes them easier to study and to solve, and proving that these problems are hard suffices to show that more complex problems are hard as well. ==Examples== Important undecidable decision problems include the halting problem and Goodstein's theorem; for more, see list of undecidable problems. In complexity theory (computation), decision problems which are complete problem are used to characterize complexity classes of decision problems. Important examples include the boolean satisfiability problem and several of its variants, along with the undirected reachability problem and directed reachability problem. Computability Logic
Since the definition of "decision problem" refers to the idea of "problem", I think we should have a page defining what that is. ==Complete rewrite== I did a complete rewrite of the article. The main problems I tried to fix were #article to verbose without using any well defined concepts #mixed word problem (computability) with general concept of decision problem, which I think should be separate User:MathMartin 13:46, 19 Nov 2004 (UTC) :I like the brevity, but it seems to focus strongly on computability theory, particularly in the examples section. I'll add some example problems important in complexity theory and make a note that the list is only a few important examples. User:Dcoetzee 18:55, 19 Nov 2004 (UTC) ---- I've edited again because there is a difference between computability and decidability. I've also created a similar looking computation problem stub. The class of decidable problems is reducible to the class of computable functions. We should add interesting classes of questions that are decidable. I.e., subsets of the predicate calculus that are decidable (i.e. monadic predicate logic, all valid formulas, etc.), the propositional calculus, trivially any finite set (not so interesting I suppose), and so on. User:Nortexoid 02:02, 23 Nov 2004 (UTC)
See other meanings of words starting from letter:
Words begining with Decision_problem:
Decision_problem
Decision_problem
Decision_problems
Decision problem
In logic, a decision problem is determining whether or not there exists a decision procedure or algorithm for a class S of questions requiring a Boolean value (i.e., a ''true'' or ''false'', or ''yes'' or ''no''). These are also known as yes-or-no questions. For example, the decision problem for the class of questions "Does ''x'' divide ''y'' without remainder?" is ''decidable'' because there exists a mechanical procedure, namely long division, which allows us to determine for any ''x'' and any ''y'' whether the answer for "Does ''x'' divide ''y'' without remainder?" is ''yes'' or ''no''. Every decision problem is reducible to a computation problem in the following way. Every class of yes-or-no questions is reducible to the predicate form "Is true?". For example, the above example is reducible to "Is true?". This predicate form is reducible to the representing function So deciding whether is true is equivalent to computing the value for . ==Definition== A decision problem is a countable set ''S'' and a function_(mathematics) :. Let ''A'' be the preimage of ''f'' for 0. : The problem is called decidable if ''A'' is a recursive set. It is called partially decidable, solvable or provable if ''A'' is a recursively enumerable set. Otherwise, the problem is called undecidable. We can give an alternative definition in terms of computable functions: If ''f'' is a total function computable function, the problem is called computable. If ''f'' is only a partial function computable function, the problem is called partially computable. Otherwise, the problem is called uncomputable. ==Notes== It should be noted that a decision problem is always a set of related problems which is in some sense large enough. A single problem ''P'' is always trivially decidable by assigning the constant function ''f''(''P'')≡0 or ''f''(''P'')≡1 to it. Nearly every problem can be cast as a decision problem by using reduction (complexity)s, often with little effect on the amount of time or space needed to solve the problem. Many traditional hard problems have been cast as decision problems because this makes them easier to study and to solve, and proving that these problems are hard suffices to show that more complex problems are hard as well. ==Examples== Important undecidable decision problems include the halting problem and Goodstein's theorem; for more, see list of undecidable problems. In complexity theory (computation), decision problems which are complete problem are used to characterize complexity classes of decision problems. Important examples include the boolean satisfiability problem and several of its variants, along with the undirected reachability problem and directed reachability problem. Computability Logic
Decision problem
Since the definition of "decision problem" refers to the idea of "problem", I think we should have a page defining what that is. ==Complete rewrite== I did a complete rewrite of the article. The main problems I tried to fix were #article to verbose without using any well defined concepts #mixed word problem (computability) with general concept of decision problem, which I think should be separate User:MathMartin 13:46, 19 Nov 2004 (UTC) :I like the brevity, but it seems to focus strongly on computability theory, particularly in the examples section. I'll add some example problems important in complexity theory and make a note that the list is only a few important examples. User:Dcoetzee 18:55, 19 Nov 2004 (UTC) ---- I've edited again because there is a difference between computability and decidability. I've also created a similar looking computation problem stub. The class of decidable problems is reducible to the class of computable functions. We should add interesting classes of questions that are decidable. I.e., subsets of the predicate calculus that are decidable (i.e. monadic predicate logic, all valid formulas, etc.), the propositional calculus, trivially any finite set (not so interesting I suppose), and so on. User:Nortexoid 02:02, 23 Nov 2004 (UTC)
See other meanings of words starting from letter:
D
DA | DB | DC | DE | DF | DG | DH | DI | DJ | DK | DL | DM | DN | DO | DP | DR | DS | DT | DU | DW | DX | DY | DZ |Words begining with Decision_problem:
Decision_problem
Decision_problem
Decision_problems
Sponsored links: praca, nurkowanie.
These materials are based on Wikipedia and licensed under the GNU FDL
YouTube.com videos better site than Turbo Tax 2007
