| Decision Problem |
Article Index for Decision |
Website Links For Decision |
Information AboutDecision Problem |
| CATEGORIES ABOUT DECISION PROBLEM | |
| logic | |
| theory of computation | |
| computational problems | |
| recursion theory | |
|
For example, we might have a decision problem "given two numbers ''x'' and ''y'', does ''x'' evenly divide ''y''?". This is a yes-or-no question, and its answer depends on the values of ''x'' and ''y''. An algorithm for this decision problem would tell us how, given ''x'' and ''y'', we can determine whether ''x'' evenly divides ''y''. Decision problems are somewhat less intuitively useful than function problems, which are allowed to have any answers, not just yes-or-no answers. For example, a function problem might be "given two numbers ''x'' and ''y'', what is ''x'' divided by ''y''?". However, computational complexity theory has typically found it easier to study decision problems. In complexity theory, we attempt to categorize decision problems based on how "difficult" they are, in terms of the Computational Resource s needed by the most efficient algorithms for that decision problem. DEFINITION A ''decision problem'' is any arbitrary yes-or-no question on an infinite set of inputs. Because of this, it is traditional to define the decision problem in terms of the set of inputs for which the problem returns ''yes''. In this sense, a decision problem is equivalent to a Formal Language . Formally, a decision problem is a Countable Set ''S'' and a Function : Let ''A'' be the Preimage of ''f'' for 1: |
|
|